
// NEW: the mixture of AC3.0 and AC3.1
// all methods are named as *_residue*
// 5 Apr 2004

// NEW: the AC3.0 with cache is implemented
// all methods are named as *_cache*
// 3 Apr 2004

// This MAC version is converted from an earlier standalone
// version of AC3 algo's developed for IJCAI-01 paper:
// Making AC3 optimal.
// 14 Feb 2004

// The O(ed) space method to implement AC3.1 is added
// on 15 Feb 2004 

/* 
   initialization of 'support' is move from ac3_init() to CSP_Ac3()
*/

#include "mac3all-k-residue.h"
#include <errno.h>

FilterQueue::FilterQueue(int n1) : n(n1), length(n1+1)
{
  int i;

  // we have only n^2+1 slots in the Q. 
  // Each constraint can occupy one and only one
  // slot in the Q. so we need another
  // array to record the status of each constraint.

  // Q = (Qentry  *) malloc( sizeof( Qentry) * length );
  Q = new Qentry [length];
  if (!Q){
    printf (" Mem error Q\n");
    exit(-1);
  }
  head = tail = 0;
  
  int *statusp;
  
  // status is to prevent a constraint enter queue twice
  // status = (int *) malloc (sizeof(int) * length );
  status = new int [length];
  if (!status){
    printf (" Mem error (status)\n");
    exit(-1);
  }
  // enable all positions in the Q 
  for(i = 0, statusp = status; i < n; i++){
    *statusp = 0;
    statusp++;
  }
}

FilterQueue::~FilterQueue()
{
  if (Q != NULL) delete [] Q; 
  if (status != NULL) delete [] status;
  // free(Q);
  // free(status);
}

void FilterQueue::enqueue(int i)
{
  if ( !status[i] ){ // not entered before?
    status[i] = 1; // disable (i,j) to enter Q before (i,j) is dequeued
    Q[tail].i = i;
    tail = (tail + 1) % length ;
  }
}

void FilterQueue::dequeue(int &i)
{
  i = Q[head].i;
  head = (head + 1) % length;
  status[i] = 0; // enable (i,j) 
}

//--------------------AC algorithms-------------------------

// return false if csp is found not satisfied otherwise true

bool CSP_Ac3::ac3_init(FilterQueue& Q)
{
  //cout << "made it to init" << endl;
  int i, j;

  // check all constraints first time

  for(i = 0; i < n; i++)
    for(cllp = cross_link_list[i].begin();
	cllp != cross_link_list[i].end(); ++cllp){
      j = *cllp;
      if (REVISE3(i,j)){
	if (empty_domain(i)) return false; 
	//enq_neighbours(i, j);
	Q.enqueue(i); 
      }
    }
  numOfRemovedValuesB4Propogation = num_removed_values;
  return true; //so far, the CSP is Arc-consistent
}

bool CSP_Ac3::ac3_cache_init(FilterQueue& Q)
{
  int i, j, k;
  ConstraintCache* cnp;
  ConstraintCache cp;

  cnCache = new ConstraintCache [n*n];
  if (!cnCache){
    printf("Memory error (cn)\n");
    exit (-1);
  }
  for (i = 0, cnp = cnCache; i < n; i++)
    for (j = 0; j < n; j++, cnp++){
      *cnp = NULL;
    }

  // check all constraints first time

  for(i = 0; i < n; i++)
    for(cllp = cross_link_list[i].begin();
	cllp != cross_link_list[i].end(); ++cllp){
      j = *cllp;
      // setup cache for (i,j)
      cnCache[i*n+j] = (ConstraintCache) new char [d*d];
      for(k=0, cp=cnCache[i*n+j]; k < d*d; k++, cp++)
	*cp = -1; 
      if (REVISE3_cache(i,j)){
	if (empty_domain(i)) return false; 
	//enq_neighbours(i, j);
	Q.enqueue(i); 
      }
    }
  numOfRemovedValuesB4Propogation = num_removed_values;
  return true; //so far, the CSP is Arc-consistent
}

// return false if csp is found not satisfied otherwise true
// this function establishes the data to remember of 
// the last support. This is similar to the ac3_1_init ...
bool CSP_Ac3::ac3_residue_init(FilterQueue& Q) 
{
  int i, j;
  bool acConsistent = true;
  
  //----------------- allocate memory for support ------------
  // decrease the size of support, which improves the efficiency of REVISEnew1
  support = new Support [n*n];
  if (!support){
    printf (" Mem error (support) %d n=%d\n", errno, n);
    exit(-1);
  }

  // allocate memory for support wrt each constraint

  for(i = 0; i < n; i++)
    for(cllp = cross_link_list[i].begin();
	cllp != cross_link_list[i].end(); ++cllp){
      j = *cllp;
      support[i*n + j] = (Support) new int [d];
      if (!support[i*n+j]){
	printf (" Mem error (support) %d n=%d\n", errno, n);
	exit(-1);
      }     
    }
  
  //----------------- populate support[] and check AC of the csp--
  // check all constraints first time
  for(i = 0; i < n; i++)
    for(cllp = cross_link_list[i].begin();
	cllp != cross_link_list[i].end(); ++cllp){
      j = *cllp;
      if (REVISE3_1_init(i,j)){
	if (empty_domain(i)) {
	  acConsistent = false; 
	  goto cleanup;
	}
	Q.enqueue(i); 
      }
    }
 cleanup:
  numOfRemovedValuesB4Propogation = num_removed_values;
  return acConsistent; //so far, the CSP is Arc-consistent
}

// return false if csp is found not satisfied otherwise true
// this function establishes the data to remember of 
// the last support. 
bool CSP_Ac3::ac3_1_init(FilterQueue& Q) 
{
  int i, j;
  bool acConsistent = true;
  
  //----------------- allocate memory for support ------------
  // decrease the size of support, which improves the efficiency of REVISEnew1
  // support = (Support *) malloc( sizeof(Support)*(n*n));
  support = new Support [n*n];
  if (!support){
    printf (" Mem error (support) %d n=%d\n", errno, n);
    exit(-1);
  }

  // allocate memory for support wrt each constraint

  for(i = 0; i < n; i++)
    for(cllp = cross_link_list[i].begin();
	cllp != cross_link_list[i].end(); ++cllp){
      j = *cllp;
      // support[i*n + j] = (Support) malloc( sizeof(int)*d );
      support[i*n + j] = (Support) new int [d];
      if (!support[i*n+j]){
	printf (" Mem error (support) %d n=%d\n", errno, n);
	exit(-1);
      }     
    }
  
  //----------------- populate support[] and check AC of the csp--
  // check all constraints first time
  for(i = 0; i < n; i++)
    for(cllp = cross_link_list[i].begin();
	cllp != cross_link_list[i].end(); ++cllp){
      j = *cllp;
      if (REVISE3_1_init(i,j)){
	if (empty_domain(i)) {
	  acConsistent = false; 
	  goto cleanup;
	}
	Q.enqueue(i); 
      }
    }
 cleanup:
  numOfRemovedValuesB4Propogation = num_removed_values;
  return acConsistent; //so far, the CSP is Arc-consistent
}

CSP_Ac3::CSP_Ac3(int n1, int d1, int e1, int T, int *S) : CSP(n1, d1, e1, T, S)
{
  //cerr << "Constructor: MAC3 begin" << endl;
  initCSP_Ac3();
  //cerr << "Constructor: MAC3 end" << endl;
}

CSP_Ac3::CSP_Ac3(int n1, int d1) : CSP(n1, d1)
{
  initCSP_Ac3();
}

CSP_Ac3::CSP_Ac3(const char *directory) : CSP(directory)
{
  initCSP_Ac3();
}

void CSP_Ac3::initCSP_Ac3(){
  // initialization of pointers used in different algorithms,
  // assuming that none of them is used. 
  residues = NULL;
  support = NULL; 
  resD = NULL;
  fit1 = NULL;
  fit2 = NULL;
  firstRevision = NULL;
  stopValues = NULL; 
#ifdef TAIL_DOMAIN
  supportB4StopValue=NULL;
#endif
#ifdef ADAPTIVE_DOMAIN
  mac3ado_support=NULL;
#endif
  cnCache = NULL; 
  numOfRemovedValuesB4Propogation = -1;
  autofail=false;
}

// if ac3 is used, nothing is done in this destruction
CSP_Ac3::~CSP_Ac3()
{
  //cerr << "Destructor: MAC3 begin" << endl;
  int i, j;
  
  if (residues != NULL) {// Residues are used
    for(i = 0; i < n; i++)
      for(cllp = cross_link_list[i].begin();
	  cllp != cross_link_list[i].end(); ++cllp){
	j = *cllp;
      
	for(int k=0; k<d; k++){
	  if((residues[i*n + j])[k] != NULL){
	      switch(residueMethod){
	      case FIFO_simple_op:
		delete (FIFO_simple *)      (residues[i*n + j])[k];
		break;
	      case FIFO_update_op:
		delete (FIFO_update *)      (residues[i*n + j])[k];	      
		break;
	      case FIFO_full_op:
		delete (FIFO_full *)        (residues[i*n + j])[k];	      
		break;
	      case MINDOMAIN_simple_op:
		delete (MINDOMAIN_simple *) (residues[i*n + j])[k];	      
		break;
	      case MINDOMAIN_update_op:
		delete (MINDOMAIN_update *) (residues[i*n + j])[k];
		break;
	      case MAXDOMAIN_simple_op:
		delete (MAXDOMAIN_simple *) (residues[i*n + j])[k];	      
		break;
	      case MAXDOMAIN_update_op:
		delete (MAXDOMAIN_update *) (residues[i*n + j])[k];	      
		break;
	      case MINLEVEL_simple_op:
		delete (MINLEVEL_simple *)  (residues[i*n + j])[k];	      
		break;
	      case MINLEVEL_update_op:
		delete (MINLEVEL_update *)  (residues[i*n + j])[k];	      
		break;
	      case MAXLEVEL_simple_op:
		delete (MAXLEVEL_simple *)  (residues[i*n + j])[k];	      
		break;
	      case MAXLEVEL_update_op:
		delete (MAXLEVEL_update *)  (residues[i*n + j])[k];	      
		break;
	      case MINUSE_update_op:
		delete (MINUSE_update *)    (residues[i*n + j])[k];	      
		break;
	      case MINUSE_full_op:
		delete (MINUSE_full *)      (residues[i*n + j])[k];	      
		break;
	      case MAXUSE_update_op:
		delete (MAXUSE_update *)    (residues[i*n + j])[k];	      
		break;
	      case MAXUSE_full_op:
		delete (MAXUSE_full *)      (residues[i*n + j])[k];	      
		break;
	      default:
		cout << "Wrong configuration of the residue polocy." << endl;
	      } // switch
	  } // if not NULL
	} // k
	delete [] residues[i*n + j];
      } // j
    delete [] residues; 
  }

  // printf("&support=%x when its destroyed", support);
  if (support != NULL) { // AC3.1 is used (mac3_1 is used)
    for(i=0; i < n; i++)
      for(cllp = cross_link_list[i].begin();
	  cllp != cross_link_list[i].end(); ++cllp){
	j = *cllp;
	if(support[i*n + j] != NULL) delete [] support[i*n+j];
      }
    
    delete [] support; // release the support space for AC3.1 like algorithms
  }
  if (resD != NULL) { // AC3.1 is used (mac3_1 is used)
    for(i=0; i < n; i++)
      for(cllp = cross_link_list[i].begin();
	  cllp != cross_link_list[i].end(); ++cllp){
	j = *cllp;
	if(resD[i*n + j] != NULL) delete [] resD[i*n+j];
      }
    
    delete [] resD; // release the support space for AC3.1 like algorithms
  }

   if (fit1 != NULL) { // AC3.1 is used (mac3_1 is used)
    for(i=0; i < n; i++)
      for(cllp = cross_link_list[i].begin();
	  cllp != cross_link_list[i].end(); ++cllp){
	j = *cllp;
	if(fit1[i*n + j] != NULL) delete [] fit1[i*n+j];
      }
    
    delete [] fit1; // release the support space for AC3.1 like algorithms
  }
  if (fit2 != NULL) { // AC3.1 is used (mac3_1 is used)
    for(i=0; i < n; i++)
      for(cllp = cross_link_list[i].begin();
	  cllp != cross_link_list[i].end(); ++cllp){
	j = *cllp;
	if(fit2[i*n + j] != NULL) delete [] fit2[i*n+j];
      }
    
    delete [] fit2; // release the support space for AC3.1 like algorithms
  }


#ifdef ADAPTIVE_DOMAIN
  if (mac3ado_support != NULL) { // AC3ADO is used
    for(i=0; i < n; i++)
      for(cllp = cross_link_list[i].begin();
	  cllp != cross_link_list[i].end(); ++cllp){
	j = *cllp;
	if(mac3ado_support[i*n + j] != NULL) delete [] mac3ado_support[i*n+j];
      }
    
    delete [] mac3ado_support; // release the support space for AC3ADO like algorithms
  }
#endif


  // release cache space for ac3_cache algo.
  if(cnCache != NULL){ // AC3.1 is used (mac3_1 is used)
    for(i=0; i < n; i++)
      for(cllp = cross_link_list[i].begin();
	  cllp != cross_link_list[i].end(); ++cllp){
	j = *cllp;
	if(cnCache[i*n + j] != NULL) delete [] cnCache[i*n+j];
      }
    
    delete [] cnCache; // release cache space ac3_cache
  }

  // these are for mac3.1.1
  if( firstRevision != NULL) delete [] firstRevision; 
  if( stopValues != NULL) delete [] stopValues;
#ifdef TAIL_DOMAIN
  if( supportB4StopValue != NULL) delete [] supportB4StopValue;
#endif
  //cerr << "Destructor: MAC3 end" << endl;
}

//consistency is enforced on arc (i,j)
bool CSP_Ac3::REVISE3(int i, int j)
{
  int x, y;  

  Domain *dip, *djp;
  bool DELETE, viable;

  DELETE = false; // no value is removed
  dip = domainOfVar(i); // domain + i*(d+1);
  djp = domainOfVar(j); // domain + j*(d+1);

  // curij: the matrix of relation (i,j)

  for(x = dip[0].next; x != 0; x = dip[x].next){
    viable = false;
    for( y = djp[0].next; y != 0; y = djp[y].next){
      num_cchecks++;
#ifdef EXTENDED_STATISTICS
	  ccheck_levels[curPhase+1]++;
#endif
      if (validtuple(i, j, x, y)) {
	viable = true;
	break;
      }
    }
    if (!viable){ // no support
      remove(i,x);
      DELETE = true; // some value in x is removed
    }
  } // all values in i
  return DELETE;
}

//consistency is enforced on arc (i,j)
bool CSP_Ac3::REVISE3_cache(int i, int j)
{
  int x, y;  

  Domain *dip, *djp;
  bool DELETE, viable;

  DELETE = false; // no value is removed
  dip = domainOfVar(i); // domain + i*(d+1);
  djp = domainOfVar(j); // domain + j*(d+1);

  // curij: the matrix of relation (i,j)
  ConstraintCache CCcurij;

  for(x = dip[0].next, CCcurij = cnCache[i*n + j] + (x-1)*d; 
      x != 0; x = dip[x].next, CCcurij = cnCache[i*n + j] + (x-1)*d){
    viable = false;
    for( y = djp[0].next; y != 0; y = djp[y].next){
      num_cchecks++;
#ifdef EXTENDED_STATISTICS
	  ccheck_levels[curPhase+1]++;
#endif
      if (CCcurij[y-1] == 1) {
	viable = true;
	break;
      }
      else // the cache part is added on 3 Apr 2004
	if (CCcurij[y-1] == -1) { // not in the cache yet
		num_cchecks++;
#ifdef EXTENDED_STATISTICS
	    ccheck_levels[curPhase+1]++;
#endif
	  if (validtuple(i, j, x, y)){ // (x,y) belons to c_{ij}?
	    CCcurij[y-1] = 1;
	    viable = true;
	    break;
	  }
	  else CCcurij[y-1] = 0; 
	} 
    }
    if (!viable){ // no support
      remove(i,x);
      DELETE = true; // some value in x is removed
    }
  } // all values in i
  return DELETE;
}

// THe new instance of AC-3 will employ REVISEnew1
// in its initialization phase and REVISEnew2 in
// propagation phase.

// The reason to use a seperate
// This REVISE is used only in the initialization of ac3_1
// to initialize support[i,a,j].
bool CSP_Ac3::REVISE3_1_init(int i, int j)
{
  int x, y;
  Domain *dip, *djp;
  Support sp;
  bool DELETE, viable;

  DELETE = false; // no value is removed
  dip = domainOfVar(i); //domain + i*(d+1);
  djp = domainOfVar(j); //domain + j*(d+1);
  // v2: move sp out from the following for loop
  sp = support[i*n + j] ;

  // curij: the matrix of relation (i,j)

  // printf ("\nchecking (%d,%d):", i, j );
  // note: curij(x,y) means (x+1, y+1) satisfy constraint (i,j)
  // the first element in domain of i is 1 rather than 0.
  // the content of sp[i,j,x-1] is y(from 1 to d)

  // v2: move curij into for control statement
  for(x = dip[0].next; x != 0; x = dip[x].next){
    viable = false;
    // printf("%d ", x);
    for( y = djp[0].next; y != 0; y = djp[y].next){
      num_cchecks++;
#ifdef EXTENDED_STATISTICS
	  ccheck_levels[curPhase+1]++;
#endif
      if (validtuple(i,j,x,y)) {
	viable = true;
	sp[x-1] = y;
	break;
      }
    }
    if (!viable){
      remove(i,x);
      DELETE = true; // some value in x is removed
    }
  } // all values in i
  return DELETE;
}

// This REVISE is used in the propogation phase ac3_residue.
// similar to RESIE of ac3.1
bool CSP_Ac3::REVISE3_residue_propogate(int i, int j)
{
  int x, y;
  Domain *dip, *djp;
  Support sp;
  int DELETE, viable;

  DELETE = false; // no value is removed
  dip = domainOfVar(i); // domain + i*(d+1);
  djp = domainOfVar(j); // domain + j*(d+1);

  // curij: the matrix of relation (i,j)
  // std::cout << "i=" << i << " j=" << j << " x=" << x << '\n';
  //  if( (x > 30) || (x <= 0)) 
  //    std::cout << "x=" << x << " is spoiled\n"; 
  //  if ((y == 30) || (y == 0)){
  //    std::cout << "support is spoiled\n"; 
  //    std::cout << "i=" << i << " j=" << j << " x=" << x << " y=" << y << '\n';
  //  }

  // printf ("\nchecking (%d,%d):", i, j );
  for(x = dip[0].next, sp = support[i*n + j]; x != 0; x = dip[x].next){
    
    y = sp[x-1];
	num_dchecks++;
#ifdef EXTENDED_STATISTICS
	dcheck_levels[curPhase+1]++;
#endif
    if (! djp[y].yes){ // is the support of x no longer valid?
      viable = false;
      // we start to search a support from scratch
      for( y = djp[0].next; y != 0; y = djp[y].next){
		num_cchecks++;
#ifdef EXTENDED_STATISTICS
	   ccheck_levels[curPhase+1]++;
#endif
	if (validtuple(i,j,x,y)) { //if y is valid 
	  viable = true;
	  sp[x-1] = y; // remember this support
	  break;
	}
      }
      if (!viable){ // no support
	remove(i,x);
	DELETE = true; // some value in x is removed
      }
    } // else x is supported

  } // all values in i
  return DELETE; 
}

bool CSP_Ac3::REVISE3_k_residue_propogate(int i, int j)
{
  int x, y;
  Domain *dip, *djp;
  Support sp;
  Residues **residuesP;
  int DELETE, viable;

  DELETE = false; // no value is removed
  dip = domainOfVar(i); // domain + i*(d+1);
  djp = domainOfVar(j); // domain + j*(d+1);

  // curij: the matrix of relation (i,j)
  // std::cout << "i=" << i << " j=" << j << " x=" << x << '\n';
  //  if( (x > 30) || (x <= 0)) 
  //    std::cout << "x=" << x << " is spoiled\n"; 
  //  if ((y == 30) || (y == 0)){
  //    std::cout << "support is spoiled\n"; 
  //    std::cout << "i=" << i << " j=" << j << " x=" << x << " y=" << y << '\n';
  //  }

  /*-- to be dedeleted Mar 9 2007 */
  // printf ("\nchecking (%d,%d):", i, j );
  residuesP = residues[i*n + j]; 
  for(x = dip[0].next, sp = support[i*n + j]; x != 0; x = dip[x].next){
    // cout << 'B'; 
    if (!residuesP[x-1]->findSupport()) { // not found in the cache
      viable = false; 
      // we start to search a support from scratch
      for( y = djp[0].next; y != 0; y = djp[y].next){
		num_cchecks++;
#ifdef EXTENDED_STATISTICS
	   ccheck_levels[curPhase+1]++;
#endif
	if (validtuple(i,j,x,y)) { //if y is valid 
	  viable = true;
	  residuesP[x-1]->add(y); // add this support to cache
	  break;
	}
      }
      if (!viable){ // no support
	remove(i,x);
	DELETE = true; // some value in x is removed
      }
    } // else x is supported
  } // all values in i
  // cout << endl;
  // cout << "--dchecks is " << dchecks() << endl;
  return DELETE; 
}

// This REVISE is used in the propogation phase (of ac3_1) and mac3_1.
bool CSP_Ac3::REVISE3_1_propogate(int i, int j)
{
  int x, y;
  Domain *dip, *djp;
  Support sp;
  BackupedSupport backupedSupport;
  int DELETE, viable;

  //extern int curInstance;

  DELETE = false; // no value is removed
  dip = domainOfVar(i); // domain + i*(d+1);
  djp = domainOfVar(j); // domain + j*(d+1);

  // curij: the matrix of relation (i,j)
  // std::cout << "i=" << i << " j=" << j << " x=" << x << '\n';
  //  if( (x > 30) || (x <= 0)) 
  //    std::cout << "x=" << x << " is spoiled\n"; 
  //  if ((y == 30) || (y == 0)){
  //    std::cout << "support is spoiled\n"; 
  //    std::cout << "i=" << i << " j=" << j << " x=" << x << " y=" << y << '\n';
  //  }

  // printf ("\nchecking (%d,%d):", i, j );
  for(x = dip[0].next, sp = support[i*n + j]; x != 0; x = dip[x].next){
    
    y = sp[x-1];
	  num_dchecks++;
#ifdef EXTENDED_STATISTICS
	  dcheck_levels[curPhase+1]++;
#endif
    if (! djp[y].yes){ // is the support of x no longer valid?
      viable = false;
	  for( y = djp[y].next; y != 0; y = djp[y].next){
		num_dchecks++;
#ifdef EXTENDED_STATISTICS
	    dcheck_levels[curPhase+1];
#endif
		if (djp[y].yes) break;
	  }

      for( ; y != 0; y = djp[y].next){
	// if ((djp[y].yes) && (validtuple(i,j,x,y))) { //if y is valid

	  num_cchecks++;
#ifdef EXTENDED_STATISTICS
	  ccheck_levels[curPhase+1]++;
#endif
	  if (validtuple(i,j,x,y)) { 
	    viable = true;
	    //--------------------backup the old support--------------
	    
	    backupedSupport.varI = i;
	    backupedSupport.varJ = j;
	    backupedSupport.value = x;
	    backupedSupport.support = sp[x-1]; 
	    if( sp[x-1] == 0) 
	      cout << "its already spoiled before backup: \n";
	    backupedSupport.phase = curPhase; // curPhase defined in class CSP
	    previousSupports.push(backupedSupport); 
	    //-------------------- end of backup ---------------------
	    sp[x-1] = y; // remember this support
	    break;
	  }

      }
      if (!viable){ // no support
	remove(i,x);
	DELETE = true; // some value in x is removed
      }
    } // else x is supported
  } // all values in i
  return DELETE; 
}

// traditional implementation of AC-3

bool CSP_Ac3::ac3()
{
  //int i, j;
  FilterQueue Q(n); 
  //cout << "Starting AC3 (queue size " << n << ")" << endl;
  
  if (!ac3_init(Q)) return false;
  //cout << "Finished Initialize" << endl;
  
  return ac3_propogate(Q); 
}

bool CSP_Ac3::ac3_cache()
{
  //int i, j;
  FilterQueue Q(n); 
  //cout << "Starting AC3 cache" << endl;
  
  if (!ac3_cache_init(Q)) return false;
  
  return ac3_cache_propogate(Q); 
}

bool CSP_Ac3::ac3_residue()
{
  //int i, j;
  FilterQueue Q(n); 
  //cout << "Starting AC3 residue" << endl;
  
  if (!ac3_residue_init(Q)) return false;
  
  return ac3_residue_propogate(Q); 
}

/* k-residues techniques for AC3 algorithm 
 * 8 Mar 2007
 * ac3_k_residue() uses ac3_residue to do preprocessing
 * and initialize residues[] using support[]
 */
bool CSP_Ac3::ac3_k_residue()
{
  int i, j; 

  //----------------- allocate memory for residues ------------
  // decrease the size of support, which improves the efficiency of REVISEnew1
  residues = new (nothrow) Residues ** [n*n];
  if (!residues){
    printf (" Mem error (support) %d n=%d\n", errno, n);
    exit(-1);
  }

  // pass the current problem instance to residues
  // type conversion: static_cast <BT *>(this)?
  Residues::setCSP(reinterpret_cast <BT *>(this)); 

  // allocate memory for residues wrt each constraint

  for(i = 0; i < n; i++)
    for(cllp = cross_link_list[i].begin();
	cllp != cross_link_list[i].end(); ++cllp){
      j = *cllp;
      residues[i*n + j] =  new (nothrow) Residues * [d];
      if (!residues[i*n+j]){
	printf (" Mem error (support) %d n=%d\n", errno, n);
	exit(-1);
      }     
      for(int k=0; k<d; k++)
	(residues[i*n + j])[k] = NULL; 
    }
  
  // the deconstruction of residues
  // will be adaptive: that's destruct what has  be contructed  

  FilterQueue Q(n); 
 
  if (!ac3_residue_init(Q)) return false;
  
  bool acConsistency;
  acConsistency = ac3_residue_propogate(Q); 
  if (!acConsistency) return false;

  // initialize residues
  for(i = 0; i < n; i++)
    for(cllp = cross_link_list[i].begin();
	cllp != cross_link_list[i].end(); ++cllp){
      j = *cllp;
      
      // produce cache for every a of D_i wrt c_{ij}
      for(int k=0; k<d; k++){
	bool legalOp = true;
	if(isValid(i, k+1)){
	  try{
	    switch(residueMethod){
	    case FIFO_simple_op:
	      (residues[i*n + j])[k] =  new FIFO_simple;	      
	      break;
	    case FIFO_update_op:
	      (residues[i*n + j])[k] =  new FIFO_update;	      
	      break;
	    case FIFO_full_op:
	      (residues[i*n + j])[k] =  new FIFO_full;	      
	      break;
	    case MINDOMAIN_simple_op:
	      (residues[i*n + j])[k] =  new MINDOMAIN_simple;	      
	      break;
	    case MINDOMAIN_update_op:
	      (residues[i*n + j])[k] =  new MINDOMAIN_update;	 
	      break;
	    case MAXDOMAIN_simple_op:
	      (residues[i*n + j])[k] =  new MAXDOMAIN_simple;	      
	      break;
	    case MAXDOMAIN_update_op:
	      (residues[i*n + j])[k] =  new MAXDOMAIN_update;	      
	      break;
	    case MINLEVEL_simple_op:
	      (residues[i*n + j])[k] =  new MINLEVEL_simple;	      
	      break;
	    case MINLEVEL_update_op:
	      (residues[i*n + j])[k] =  new MINLEVEL_update;	      
	      break;
	    case MAXLEVEL_simple_op:
	      (residues[i*n + j])[k] =  new MAXLEVEL_simple;	      
	      break;
	    case MAXLEVEL_update_op:
	      (residues[i*n + j])[k] =  new MAXLEVEL_update;	      
	      break;
	    case MINUSE_update_op:
	      (residues[i*n + j])[k] =  new MINUSE_update;	      
	      break;
	    case MINUSE_full_op:
	      (residues[i*n + j])[k] =  new MINUSE_full;	      
	      break;
	    case MAXUSE_update_op:
	      (residues[i*n + j])[k] =  new MAXUSE_update;	      
	      break;
	    case MAXUSE_full_op:
	      (residues[i*n + j])[k] =  new MAXUSE_full;	      
	      break;
	    default:
	      cout << "Wrong configuration of the residue polocy." << endl;
	      legalOp = false;
	    } // switch
	  } 
	  catch(bad_alloc){
	    cerr << "Memory allocation error." << endl;
	  } // try ... catch
	  if(legalOp){ // for value k+1 of D_i
	    (residues[i*n+j])[k]->initialize(cacheSize, i, j, k+1);
	    (residues[i*n+j])[k]->initAdd((support[i*n+j])[k]);
	  }
	} // if isValid
      } // k
    } // j

  return true;
}

bool CSP_Ac3::ac3_propogate(FilterQueue& Q) {
	
  if(autofail)
  {
    autofail=false;
    return false;
  }
  // variables i and j
  int i, j;

  // std::cout << "removed value is %d \npropagation is on ...", num_removed_values);
  while ( !Q.empty()){
    Q.dequeue(j);

    for(cllp = cross_link_list[j].begin();
	cllp != cross_link_list[j].end(); ++cllp){
      i = *cllp;

      if (isAssigned(i)) continue; // var i being instantiated, ommit it

      if (REVISE3(i,j)){
	if (empty_domain(i)) return false;

	//enq_neighbours(i, j);
	Q.enqueue(i);
      } // the domain of i is revised
    } // all neigbouring variables of var j
  } // propogate all the vars in Q

  return true;
}

bool CSP_Ac3::ac3_cache_propogate(FilterQueue& Q) {
  
  if(autofail)
  {
	  autofail=false;
	  return false;
  }
  // variables i and j
  int i, j;

  // std::cout << "removed value is %d \npropagation is on ...", num_removed_values);
  while ( !Q.empty()){
    Q.dequeue(j);

    for(cllp = cross_link_list[j].begin();
	cllp != cross_link_list[j].end(); ++cllp){
      i = *cllp;

      if (isAssigned(i)) continue; // var i being instantiated, ommit it

      if (REVISE3_cache(i,j)){
	if (empty_domain(i)) return false;

	//enq_neighbours(i, j);
	Q.enqueue(i);
      } // the domain of i is revised
    } // all neigbouring variables of var j
  } // propogate all the vars in Q

  return true;
}

bool CSP_Ac3::ac3_residue_propogate(FilterQueue& Q) {

  if(autofail)
  {
	  autofail=false;
	  return false;
  }
  // variables i and j
  int i, j;

  // std::cout << "removed value is %d \npropagation is on ...", num_removed_values);
  while ( !Q.empty()){
    Q.dequeue(j);

    for(cllp = cross_link_list[j].begin();
	cllp != cross_link_list[j].end(); ++cllp){
      i = *cllp;

      if (isAssigned(i)) continue; // var i being instantiated, ommit it

      if (REVISE3_residue_propogate(i,j)){
	if (empty_domain(i)) return false;

	//enq_neighbours(i, j);
	Q.enqueue(i);
      } // the domain of i is revised
    } // all neigbouring variables of var j
  } // propogate all the vars in Q

  return true;
}

bool CSP_Ac3::ac3_k_residue_propogate(FilterQueue& Q) {

  if(autofail)
  {
	  autofail=false;
	  return false;
  }
  // variables i and j
  int i, j;

  // std::cout << "removed value is %d \npropagation is on ...", num_removed_values);
  while ( !Q.empty()){
    Q.dequeue(j);

    for(cllp = cross_link_list[j].begin();
	cllp != cross_link_list[j].end(); ++cllp){
      i = *cllp;

      if (isAssigned(i)) continue; // var i being instantiated, ommit it

      if (REVISE3_k_residue_propogate(i,j)){
	if (empty_domain(i)) return false;

	//enq_neighbours(i, j);
	Q.enqueue(i);
      } // the domain of i is revised
    } // all neigbouring variables of var j
  } // propogate all the vars in Q

  return true;
}

bool CSP_Ac3::ac3_1()
{
  //int i, j;
  FilterQueue Q(n);
  //cout << "Starting AC3.1" << endl;
  
  if (!ac3_1_init(Q)) return false;
  
  return ac3_1_propogate(Q);
}

bool CSP_Ac3::ac3_1_propogate(FilterQueue& Q) {
  
  if(autofail)
  {
	  autofail=false;
	  return false;
  }
  // variables i, j
  int i, j;
  // std::cout << "removed value is" << num_removed_values 
  //	    << "\npropagation is on ...";
  while (! Q.empty()){
    Q.dequeue(j);
    
    for(cllp = cross_link_list[j].begin();
	cllp != cross_link_list[j].end(); ++cllp){
      i = *cllp;

      if (isAssigned(i)) continue; // var i being instantiated, ommit it

      if (REVISE3_1_propogate(i,j)){
	if (empty_domain(i)) return false;

	//enq_neighbours(i, j);
	Q.enqueue(i);
      }
    } // end for loop: handle all neighbours of j
  } // end while
  return true;
}

bool CSP_Ac3::ac3_1_1()
{
  //int i, j;
  FilterQueue Q(n);
  //cout << "Starting AC3.1.1" << endl;
 
  // initialization of firstRevision.
  // this could be maintained in backtracking. but given
  // the small number of constraints, we just set true 
  // for every entry in the domain at the begining of 
  // mac3.1.1
  firstRevision = new bool [n*n]; 
  stopValues = new int [n*n*d];
#ifdef TAIL_DOMAIN
  supportB4StopValue = new bool [n*n*d];
#endif
  
  // the first step is exactly the same as ac3_1. 
  if (!ac3_1_init(Q)) return false;
  //cout << "AC3.1.1 initialized, propogating" << endl;
  return ac3_1_1_propogate(Q);
}

bool CSP_Ac3::ac3_1_1_propogate(FilterQueue& Q) {

  if(autofail)
  {
	  autofail=false;
	  return false;
  }
  // variables i, j
  int i, j;

  // A new round of propogation. 
  // We set firstRevision to be true. 
  for(i = 0; i < n; i++)
    for(cllp = cross_link_list[i].begin();
	cllp != cross_link_list[i].end(); ++cllp){
      j = *cllp;
      firstRevision[i*n+j] = true;
    }

  // std::cout << "removed value is" << num_removed_values 
  //	    << "\npropagation is on ...";
  while (! Q.empty()){
    Q.dequeue(j);
    
    for(cllp = cross_link_list[j].begin();
	cllp != cross_link_list[j].end(); ++cllp){
      i = *cllp;

      if (isAssigned(i)) continue; // var i being instantiated, ommit it

      if (REVISE3_1_1(i,j)){
		  //cout << "Done Revising." << endl; /////////v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v/////////
	if (empty_domain(i)) return false;

	//enq_neighbours(i, j);
	Q.enqueue(i);
      }
    } // end for loop: handle all neighbours of j
  } // end while
  return true;
}

//mac3 is called after assigning a value to variable
bool CSP_Ac3::mac3(int var, int value){
  FilterQueue Q(n);
  Domain* dp;
  int dummyValue = headOfDomain();

  dp = domainOfVar(var); 
  for(int curP = dp[0].next; curP != dummyValue;  curP = dp[curP].next){
    if(curP != value) // remove all values except 'value'
      remove(var, curP); 
  }

  Q.enqueue(var); 
  return ac3_propogate(Q); 
}

bool CSP_Ac3::mac3(int var){
  FilterQueue Q(n);

  Q.enqueue(var); 
  return ac3_propogate(Q); 
}

bool CSP_Ac3::mac3(list<int>& var){
  FilterQueue Q(n);

  for(list<int>::iterator iter=var.begin();iter!=var.end();iter++)
	Q.enqueue(*iter); 
  return ac3_propogate(Q); 
}

bool CSP_Ac3::mac3_cache(int var, int value){
  FilterQueue Q(n);
  Domain* dp;
  int dummyValue = headOfDomain();

  dp = domainOfVar(var); 
  for(int curP = dp[0].next; curP != dummyValue;  curP = dp[curP].next){
    if(curP != value) // remove all values except 'value'
      remove(var, curP); 
  }

  Q.enqueue(var); 
  return ac3_cache_propogate(Q); 
}

bool CSP_Ac3::mac3_cache(int var){
  FilterQueue Q(n);

  Q.enqueue(var); 
  return ac3_cache_propogate(Q); 
}

bool CSP_Ac3::mac3_cache(list<int>& var){
  FilterQueue Q(n);

  for(list<int>::iterator iter=var.begin();iter!=var.end();iter++)
	Q.enqueue(*iter); 
  return ac3_cache_propogate(Q); 
}

bool CSP_Ac3::mac3_residue(int var, int value){
  FilterQueue Q(n);
  Domain* dp;
  int dummyValue = headOfDomain();

  dp = domainOfVar(var); 
  for(int curP = dp[0].next; curP != dummyValue;  curP = dp[curP].next){
    if(curP != value) // remove all values except 'value'
      remove(var, curP); 
  }

  Q.enqueue(var); 
  return ac3_residue_propogate(Q); 
}

/* mac3_k_residue(var, value): assign value to var and
 * use ac3_k_residue_propogate to finish the propagation
 */

bool CSP_Ac3::mac3_k_residue(int var, int value){
  FilterQueue Q(n);
  Domain* dp;
  int dummyValue = headOfDomain();
  
  dp = domainOfVar(var); 
  for(int curP = dp[0].next; curP != dummyValue;  curP = dp[curP].next){
    if(curP != value) // remove all values except 'value'
      remove(var, curP); 
  }

  Q.enqueue(var); 
  return ac3_k_residue_propogate(Q); 
}

/* mac3_k_residue(var): use ac3_k_residue_propagate() to 
 * achive arc consistency when some value has been removed from domain 
 * of var (e.g., in traditional MAC by Freuder et al. )
 */
bool CSP_Ac3::mac3_k_residue(int var){
  FilterQueue Q(n);

  Q.enqueue(var); 
  return ac3_k_residue_propogate(Q); 
}

/* mac3_k_residue(var): use ac3_k_residue_propogate() to 
 * achieve AC when the domains of the variables of the list var. 
 */
bool CSP_Ac3::mac3_k_residue(list<int>& var){
  FilterQueue Q(n);

  for(list<int>::iterator iter=var.begin();iter!=var.end();iter++)
	Q.enqueue(*iter); 
  return ac3_k_residue_propogate(Q); 
}



bool CSP_Ac3::mac3_residue(int var){
  FilterQueue Q(n);

  Q.enqueue(var); 
  return ac3_residue_propogate(Q); 
}

bool CSP_Ac3::mac3_residue(list<int>& var){
  FilterQueue Q(n);

  for(list<int>::iterator iter=var.begin();iter!=var.end();iter++)
	Q.enqueue(*iter); 
  return ac3_residue_propogate(Q); 
}

// mac3_1 is called after assigning a value to a variable.
bool CSP_Ac3::mac3_1(int var, int value){
  FilterQueue Q(n);
  Domain* dp;
  int dummyValue = headOfDomain();


  dp = domainOfVar(var); 
  for(int curP = dp[0].next; curP != dummyValue;  curP = dp[curP].next){
    if(curP != value) // remove all values except 'value'
      remove(var, curP); 
  }

  Q.enqueue(var); 
  return ac3_1_propogate(Q); 
}

bool CSP_Ac3::mac3_1(int var){
  FilterQueue Q(n);

  Q.enqueue(var); 
  return ac3_1_propogate(Q); 
}

bool CSP_Ac3::mac3_1(list<int>& var){
  FilterQueue Q(n);

  for(list<int>::iterator iter=var.begin();iter!=var.end();iter++)
	Q.enqueue(*iter); 
  return ac3_1_propogate(Q); 
}

// restore support list for AC3.1
// just before (not including) the 'phase'. 'before' is smaller here.
void CSP_Ac3::restoreMAC3_1(int phase) {

  BackupedSupport backuped;
  
  while (!previousSupports.empty()) {
    backuped = previousSupports.top(); 
    if (backuped.phase < phase) break; // no more states to restore 
    (support[backuped.varI*n + backuped.varJ])[backuped.value-1] = backuped.support;
    previousSupports.pop();
  }
}

// mac3_1 is called after assigning a value to a variable.
bool CSP_Ac3::mac3_1_1(int var, int value){
  FilterQueue Q(n);
  Domain* dp;
  int dummyValue = headOfDomain();
  //int j;

  dp = domainOfVar(var); 
  for(int curP = dp[0].next; curP != dummyValue;  curP = dp[curP].next){
    if(curP != value) // remove all values except 'value'
      remove(var, curP); 
  }

  Q.enqueue(var); 
  return ac3_1_1_propogate(Q); 
}

bool CSP_Ac3::mac3_1_1(int var){
  FilterQueue Q(n);

  Q.enqueue(var); 
  return ac3_1_1_propogate(Q); 
}

bool CSP_Ac3::mac3_1_1(list<int>& var){
  FilterQueue Q(n);

  for(list<int>::iterator iter=var.begin();iter!=var.end();iter++)
	Q.enqueue(*iter); 
  return ac3_1_1_propogate(Q); 
}


#ifdef TAIL_DOMAIN

bool CSP_Ac3::REVISE3_1_1(int i, int j)
{
	//cout << "Revising " << endl; /////////v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v/////////
  int x, y, stopValue; 
  Domain *dip, *djp;
  Support sp;
  int DELETE, viable, indexBase;

  //extern int curInstance;

  DELETE = false; // no value is removed
  dip = domainOfVar(i); // domain + i*(d+1);
  djp = domainOfVar(j); // domain + j*(d+1);
  indexBase = i*n*d + j*d; 

  //bool supportB4StopValue; /////////v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v/////////
  // curij: the matrix of relation (i,j)
  // std::cout << "i=" << i << " j=" << j << " x=" << x << '\n';
  //  if( (x > 30) || (x <= 0)) 
  //    std::cout << "x=" << x << " is spoiled\n"; 
  //  if ((y == 30) || (y == 0)){
  //    std::cout << "support is spoiled\n"; 
  //    std::cout << "i=" << i << " j=" << j << " x=" << x << " y=" << y << '\n';
  //  }

  // printf ("\nchecking (%d,%d):", i, j );

  /*
  if ((debugFlag) && (i == 5) && (j==4)) {
    printDomain(i);
    printDomain(j);
  }
  */ 

  //  cout << "domain[" << i << "]=" << vars[i].domainSize << '\n';

  for(x = dip[0].next, sp = support[i*n + j] ; 
      x != 0; x = dip[x].next){

    // printf("%d ", x);
   
    viable = false; 
	//cout << "Testing Revision of " << x << endl; /////////v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v/////////
    //cout << "X.next is " << dip[x].next<< endl; /////////v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v/////////
	if (firstRevision[i*n + j]){
      // There are many choices here.
      // 1. let y=0, we start from scratch. this is good
      //    if the domain size is small. but worst case
      //    of the algorithm would be O(ed^2)!
      // 2. We start from y, dp[y].next,  ... until
      //    find the first value avail in the domain, 
      //    and then search a support starting from that value
      //    but we do this only once at the start of the assignment a new value to
      //    the current var after the previous assignment fails. 
      //    PROBLEM: the stop value found in this way is not safe becos
      //             later, this value may be removed. 
      //    SOLUTION: we just set y=0
      //    
      ///     A time stamp mechanism 
      //      is necessary for this. In this case we only 
      //      need to backup the revised variables and their
      //      time stamp (the phase). 
      // we use 2 without further time stamp. 

      // following the .next field of a deleted value, we can either 
      // reach a value in CURRENT domain or 0;
      
      // we always search a support from after the stopValue
      // and thus we set the following to be false. 10 Apr
      supportB4StopValue[indexBase + x-1] = false; 
	//cout << "Past supportB4" << endl; /////////v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v/////////

      y = sp[x-1]; // normally sp[x-1] is just a previous support
#ifdef EXTENDED_STATISTICS
		dcheck_levels[curPhase+1]++;
#endif
		num_dchecks++;
      if(djp[y].yes) {
	stopValues[indexBase + x-1] = djp[y].pre;
	viable = true; 
      }
      else {
	// find the first value, avail in current domain, after y 
	for ( y = djp[y].next; y != 0; y = djp[y].next,
#ifdef EXTENDED_STATISTICS
		dcheck_levels[curPhase+1]++,
#endif
		num_dchecks++)
	  if ( djp[y].yes) break; 
	
	// now y is eigther a valid value of D_y or 0
	// the stop value should be the previous one of y
	stopValues[indexBase + x-1] = djp[y].pre; 

	// find the first support after y 
	stopValue = stopValues[indexBase + x-1]; // eigther a value in the domain or 0    
	
	for( y=djp[stopValue].next; y != stopValue; y = djp[y].next){
	  if (y == 0) {
	    supportB4StopValue[indexBase + x-1] = true; // now y is b4 stopValue
	    continue; // We have to skip the dummy value 0
	  }


#ifdef EXTENDED_STATISTICS
	  ccheck_levels[curPhase+1]++;
#endif
	  num_cchecks++;
	  if (validtuple(i,j,x,y)) { //if y is support
	    viable = true;
	    sp[x-1] = y; // remember this support
	    break;
	  }
	} // end of for loop on y of domain j, trying to find a support for x
 	if(!viable) {// We havn't checked stopValue yet
	  if (stopValue != 0)
	  {
#ifdef EXTENDED_STATISTICS
			dcheck_levels[curPhase+1]++;
#endif
			num_dchecks++;
			if ((djp[stopValue].yes))
			{
#ifdef EXTENDED_STATISTICS
				ccheck_levels[curPhase+1]++;
#endif
				num_cchecks++;
				if((validtuple(i,j,x,stopValue))) { //if y is valid 
			 viable = true;
			 sp[x-1] = stopValue; // remember this support
			}
	    }
	  }
	}
     } // end of the case when sp[x-1] is no longer a valid domain value
	  //cout << "end of first revision." << endl; /////////v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v/////////
    } // end of the first revision of arc (i,j)
    else { 
		//cout << "Not first revision." << endl; /////////v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v/////////
      y = sp[x-1]; // second time to revise (i,j), so let y be the previous support
#ifdef EXTENDED_STATISTICS
	  dcheck_levels[curPhase+1]++;
#endif
	  num_dchecks++;
      if (djp[y].yes) viable = true;  // the support of x is still valid
      else{
	stopValue = stopValues[indexBase + x-1]; // eigther a value in the domain or 0    

	if (stopValue != y) { // there is more value in the domain  
	  bool noSupport = false;
	  if (stopValue != 0) { // in this case the stored stopValue may be removed
#ifdef EXTENDED_STATISTICS
		dcheck_levels[curPhase+1]++;
#endif
		num_dchecks++;
	    if (!djp[stopValue].yes) { // stopValue has been removed!
	      // So we need to find a new stopValue in the current domain.
	      // Here we make use of a property of function remove() and the structure
	      // of Domain that following .pre field of a value, we can always find 
	      // a valid value before the value of concern, and we arrive at 0.
	      for(stopValue = djp[stopValue].pre; stopValue != 0; stopValue = djp[stopValue].pre,
#ifdef EXTENDED_STATISTICS
			dcheck_levels[curPhase+1]++,
#endif
			num_dchecks++)
		if (djp[stopValue].yes) break; // find a stop value in current domain
	      stopValues[indexBase + x-1] = stopValue;
	    } // reset the backuped stopValue
	  }
	

	  // similarly, we find a valid value just preceding current y. 10 Apr
	  for(y = djp[y].pre; y != 0; y = djp[y].pre,
#ifdef EXTENDED_STATISTICS
	  dcheck_levels[curPhase+1]++,
#endif
	  num_dchecks++)
	    if (djp[y].yes) break; // find a stop value in current domain

	  // now stopValue is either 0 or a value in current domain
	  if ((supportB4StopValue[indexBase + x-1]) && (stopValue == y))
	    // this y has been checked before, not a support of x
	    noSupport = true;

	  if( !noSupport) { // try to find a support
	    // y has be checked, and thus we start from it successor.
	    for( y = djp[y].next; y != stopValue; y = djp[y].next){
	      if (y == 0) {
		supportB4StopValue[indexBase + x-1] = true;
		continue; // We have to skip the dummy value 0
	      }
#ifdef EXTENDED_STATISTICS
			dcheck_levels[curPhase+1]++;
#endif
	      	num_dchecks++;
	      if ((djp[y].yes))
		  {
#ifdef EXTENDED_STATISTICS
			  ccheck_levels[curPhase+1]++;
#endif
			  num_cchecks++; 
			  if((validtuple(i,j,x,y))) { //if y is valid 
			viable = true;
			sp[x-1] = y; // remember this support
			break;
			 }
		  }
	    } // end for loop on y 
	    
	    if(!viable) {// We havn't checked stopValue yet
	      if (stopValue != 0)
		  {
#ifdef EXTENDED_STATISTICS
				dcheck_levels[curPhase+1]++;
#endif
				num_dchecks++;
				if ((djp[stopValue].yes))
				{
#ifdef EXTENDED_STATISTICS
					ccheck_levels[curPhase+1]++;
#endif
					num_cchecks++;
					if((validtuple(i,j,x,stopValue))) { //if y is valid 
					  viable = true;
					  sp[x-1] = stopValue; // remember this support
					}
				}
		  }
	    }
	  } // otherwise no support
	} // otherwise no more support
      }// end of handling djp[y].yes = false
    } //end of the non-first revision of arc (i,j)
     
    if (!viable){ // no support for x
      remove(i,x);
      DELETE = true; // some value in x is removed
    }
  } // for loop on value x in domain of var i
  //cout << "finished with " << i << "->" << j << endl;
  firstRevision[i*n + j] = false;
  return DELETE; 

}

#else

bool CSP_Ac3::REVISE3_1_1(int i, int j)
{
  int x, y, stopValue; 
  Domain *dip, *djp;
  Support sp;
  int DELETE, viable, indexBase;

  DELETE = false; // no value is removed
  dip = domainOfVar(i); // domain + i*(d+1);
  djp = domainOfVar(j); // domain + j*(d+1);
  indexBase = i*n*d + j*d; 

  // curij: the matrix of relation (i,j)
  // std::cout << "i=" << i << " j=" << j << " x=" << x << '\n';
  //  if( (x > 30) || (x <= 0)) 
  //    std::cout << "x=" << x << " is spoiled\n"; 
  //  if ((y == 30) || (y == 0)){
  //    std::cout << "support is spoiled\n"; 
  //    std::cout << "i=" << i << " j=" << j << " x=" << x << " y=" << y << '\n';
  //  }

  // printf ("\nchecking (%d,%d):", i, j );
  if ((debugFlag) && (i == 5)){
    printDomain(i); 
    printDomain(j);
  }
  // cout << "domain[" << i << "]=" << vars[i].domainSize << '\n';

  for(x = dip[0].next, sp = support[i*n + j] ; 
      x != 0; x = dip[x].next){

    // printf("%d ", x);
   
    viable = false; 

    if (firstRevision[i*n + j]){
      // There are many choices here.
      // 1. let y=0, we start from scratch. this is good
      //    if the domain size is small. but worst case
      //    of the algorithm would be O(ed^2)!
      // 2. We start from y, dp[y].next,  ... until
      //    find the first value avail in the domain, 
      //    and then search a support starting from that value
      //    but we do this only once at the start of the assignment a new value to
      //    the current var after the previous assignment fails. 
      //    PROBLEM: the stop value found in this way is not safe becos
      //             later, this value may be removed. 
      //    SOLUTION: we just set y=0
      //    
      ///     A time stamp mechanism 
      //      is necessary for this. In this case we only 
      //      need to backup the revised variables and their
      //      time stamp (the phase). 
      // we use 2 without further time stamp. 

      // following the .next field of a deleted value, we can either 
      // reach a value in CURRENT domain or 0;
      y = sp[x-1]; // normally sp[x-1] is just a previous support
#ifdef EXTENDED_STATISTICS
		dcheck_levels[curPhase+1]++;
#endif
		num_dchecks++;
      if(djp[y].yes) {
	stopValues[indexBase + x-1] = djp[y].pre;
	viable = true; 
      }
      else {
	// find the first value, avail in current domain, after y 
	for ( y = djp[y].next; y != 0; y = djp[y].next,
#ifdef EXTENDED_STATISTICS
		dcheck_levels[curPhase+1]++,
#endif
		num_dchecks++)
	  if ( djp[y].yes) break; 
	
	// now y is eigther a valid value of D_y or 0
	// the stop value should be the previous one of y
	stopValues[indexBase + x-1] = djp[y].pre; 

	// find the first support after y 
	stopValue = stopValues[indexBase + x-1]; // eigther a value in the domain or 0    
	
	for( y=djp[stopValue].next; y != stopValue; y = djp[y].next){
	  if (y == 0) continue; // We have to skip the dummy value 0
	  num_cchecks++;
#ifdef EXTENDED_STATISTICS
	  ccheck_levels[curPhase+1]++;
#endif
	  if (validtuple(i,j,x,y)) { //if y is support
	    viable = true;
	    sp[x-1] = y; // remember this support
	    break;
	  }
	} // end of for loop on y of domain j, trying to find a support for x
 	if(!viable) {// We havn't checked stopValue yet
		if (stopValue != 0) {
			num_dchecks++;
#ifdef EXTENDED_STATISTICS
			dcheck_levels[curPhase+1]++;
#endif
			if ((djp[stopValue].yes)) {
			num_cchecks++;
#ifdef EXTENDED_STATISTICS
			ccheck_levels[curPhase+1]++;
#endif
				if((validtuple(i,j,x,stopValue))) { //if y is valid 
					viable = true;
					sp[x-1] = stopValue; // remember this support
				}
			}
		}
	}
     } // end of the case when sp[x-1] is no longer a valid domain value
    } // end of the first revision of arc (i,j)
    else { 
      y = sp[x-1]; // second time to revise (i,j), so let y be the previous support

	  num_dchecks++;
#ifdef EXTENDED_STATISTICS
	  dcheck_levels[curPhase+1]++;
#endif

      if (djp[y].yes) viable = true;  // the support of x is still valid
      else{
	stopValue = stopValues[indexBase + x-1]; // eigther a value in the domain or 0    

	if (stopValue != y) { // there is more value in the domain  
	  bool noSupport = false;
	  if (stopValue != 0) { // in this case the stored stopValue may be removed
		num_dchecks++;
#ifdef EXTENDED_STATISTICS
		dcheck_levels[curPhase+1]++;
#endif
	    if (!djp[stopValue].yes) { // stopValue has been removed!
	      bool supportB4StopValue = (y < stopValue);
	      // So we need to find a new stopValue in the current domain.
	      // Here we make use of a property of function remove() and the structure
	      // of Domain that following .pre field of a value, we can always find 
	      // a valid value before the value of concern, and we arrive at 0.
	      for(stopValue = djp[stopValue].pre; stopValue != 0; stopValue = djp[stopValue].pre,
#ifdef EXTENDED_STATISTICS
		dcheck_levels[curPhase+1]++,
#endif
		num_dchecks++)
		if (djp[stopValue].yes) break; // find a stop value in current domain
	      // now stopValue is either 0 or a value in current domain
	      if ((supportB4StopValue) && (stopValue < y))
		noSupport = true;
	      else
		stopValues[indexBase + x-1] = stopValue;
	    } // reset the backuped stopValue
	  }
	
	  if( !noSupport) { // try to find a support
	    // y is currently not valid, we need to find the next valid value in 
	    // domain of var j. its again a bit tricky here:
	    // y might not be a valid value in the domain
	    // but stopValue is now either 0 or a valid value.
	    // So, we have to be very careful trying to compare them using != .
	    for( y = djp[y].next; y != stopValue; y = djp[y].next){
	      if (y == 0) continue; // We have to skip the dummy value 0
	      // if ((djp[y].yes) && (validtuple(i,j,x,y))) { //if y is valid 
		  num_dchecks++;
#ifdef EXTENDED_STATISTICS
		  dcheck_levels[curPhase+1]++;
#endif
	      if (djp[y].yes){
			  num_cchecks++;
#ifdef EXTENDED_STATISTICS
			ccheck_levels[curPhase+1]++;
#endif
			if (validtuple(i,j,x,y)) { //if y is valid 
			  viable = true;
			  sp[x-1] = y; // remember this support
			  break;
			}
	      } 
	    } // end for loop on y 
	    
	    if(!viable) {// We havn't checked stopValue yet
			if (stopValue != 0) {
				 num_dchecks++;
#ifdef EXTENDED_STATISTICS
				 dcheck_levels[curPhase+1]++;
#endif
				if ((djp[stopValue].yes)) {
					num_cchecks++;
#ifdef EXTENDED_STATISTICS
					ccheck_levels[curPhase+1]++;
#endif
					if((validtuple(i,j,x,stopValue))) { //if y is valid 
					  viable = true;
					  sp[x-1] = stopValue; // remember this support
					}
				}
			}
	    }
	  } // otherwise no support
	} // otherwise no more support
      }// end of handling djp[y].yes = false
    } //end of the non-first revision of arc (i,j)
     
    if (!viable){ // no support for x
      remove(i,x);
      DELETE = true; // some value in x is removed
    }
  } // for loop on value x in domain of var i
  
  firstRevision[i*n + j] = false;
  return DELETE; 
}
#endif

void CSP_Ac3::statistics(){

  std::cout << "# of values removed before search:" << "# of values removed:" 
	    << "# of constraint checks:" << "# of domain checks" << '\n';
  std::cout << numOfRemovedValuesB4Propogation << ':' << num_removed_values << ':'
	    << (float)num_cchecks_M*ONEMILLION + num_cchecks << ':'
	    << (float)num_dchecks_M*ONEMILLION + num_dchecks << '\n'; 
#ifdef EXTENDED_STATISTICS
  std::cout << "Values removed by level:\n[";
  for(int i=0;i<n+1;i++)
	  std::cout << remval_levels[i] << ' ';
  std::cout << "]\nConstraint checks by level:\n[";
  for(int i=0;i<n+1;i++)
	  std::cout << ccheck_levels[i] << ' ';
  std::cout << "]\nDomain checks by level:\n[";
  for(int i=0;i<n+1;i++)
	  std::cout << dcheck_levels[i] << ' ';
  std::cout << "]\n";
#endif
  // << ':' << ACConsistent  
}


#ifdef ADAPTIVE_DOMAIN

bool CSP_Ac3::mac3_ADO(int var, int value){
  FilterQueue Q(n);
  Domain* dp;

  dp = domainOfVar(var); 
  for(int curP = dp[0].next; curP != 0;  curP = dp[curP].next){
    if(curP != value) // remove all values except 'value'
      remove(var, curP); 
  }

  Q.enqueue(var); 
  return ac3_ADO_propogate(Q); 
}

bool CSP_Ac3::mac3_ADO(int var){
  FilterQueue Q(n);

  Q.enqueue(var); 
  return ac3_ADO_propogate(Q);
}

bool CSP_Ac3::mac3_ADO(list<int>& var){
  FilterQueue Q(n);

  for(list<int>::iterator iter=var.begin();iter!=var.end();iter++)
	Q.enqueue(*iter); 
  return ac3_ADO_propogate(Q); 
}

bool CSP_Ac3::ac3_ADO()
{
  //int i, j;
  FilterQueue Q(n);
  //cout << "Starting AC3 ADO" << endl;
 
  // initialization of firstRevision.
  // this could be maintained in backtracking. but given
  // the small number of constraints, we just set true 
  // for every entry in the domain at the begining of 
  // mac3.1.1
  ADOSupport.generateList(n,d,e);
  mac3ado_support=new SupportNode**[n*n];
  support=new Support[n*n];
  /*if(mac3ado_support==NULL)
  {
	  cout << "Failure! Not enough memory to create residue supports!" << endl;
	  exit(1);
  }*/
  
  if (!ac3_ADO_init(Q)) return false;
  //cout << "AC3 ADO initialized, propogating" << endl;
  return ac3_ADO_propogate(Q);
}

bool CSP_Ac3::ac3_ADO_propogate(FilterQueue& Q) {

  if(autofail)
  {
	  autofail=false;
	  return false;
  }
  // variables i, j
  int i, j;

  // std::cout << "removed value is" << num_removed_values 
  //	    << "\npropagation is on ...";
  while (! Q.empty()){
    Q.dequeue(j);
    //cout << "propogating  on " << j << endl;
    for(cllp = cross_link_list[j].begin();
	cllp != cross_link_list[j].end(); ++cllp){
      i = *cllp;

      if (isAssigned(i)) continue; // var i being instantiated, ommit it

      if (REVISE3_ADO_propogate(i,j)){
		  //cout << "Done Revising." << endl; /////////v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v/////////
	if (empty_domain(i)) 
	{
		//cout << "Domain Emptied: " << i << endl;
		//getchar();
		return false;
	}

	//enq_neighbours(i, j);
	Q.enqueue(i);
      }
	  //getchar();
    } // end for loop: handle all neighbours of j
  } // end while
  return true;
}

bool CSP_Ac3::ac3_ADO_init(FilterQueue& Q) 
{
  int i, j;
  bool acConsistent = true;
  

  // allocate memory for support wrt each constraint
  //cout << "ADO init" << endl;
//  for(i = 0; i < n; i++)
//    for(cllp = cross_link_list[i].begin();
//	cllp != cross_link_list[i].end(); ++cllp){
//      j = *cllp;
//      mac3ado_support[i*n + j] = new SupportNode*[d];    
//    }
    for(i = 0; i < n; i++)
		for(j = 0; j < n; j++)
			if(related(i,j))
			{
				mac3ado_support[i*n+j] = new SupportNode*[d];
				//if(!mac3ado_support[i*n+j])
				//{
				//	cout << " Failure on memory!  Not enough to create adosupports!" << endl;
				//}
				support[i*n+j] = (Support)new int[d];
				//if(!support[i*n+j])
				//{
				//	cout << " Failure on memory!  Not enough to create adosupports!" << endl;
				//}
			}
  
  //----------------- populate support[] and check AC of the csp--
  // check all constraints first time
  for(i = 0; i < n; i++)
    for(cllp = cross_link_list[i].begin();
	cllp != cross_link_list[i].end(); ++cllp){
      j = *cllp;
      if (REVISE3_ADO_init(i,j)){
	if (empty_domain(i)) {
	  numOfRemovedValuesB4Propogation = num_removed_values;
	  return false;
	}
	//cout << i << " has changed" << endl;
	Q.enqueue(i); 
      }
    }
  numOfRemovedValuesB4Propogation = num_removed_values;
  return acConsistent; //so far, the CSP is Arc-consistent
}



bool CSP_Ac3::REVISE3_ADO_init(int i, int j)
{
	//cout << "ADO revise init: " << i << ',' << j << endl;
  int x, y;
  Domain *dip, *djp;
  SupportNode** sp;
  Support rs;
  bool DELETE, viable;

  DELETE = false; // no value is removed
  dip = domainOfVar(i); //domain + i*(d+1);
  djp = domainOfVar(j); //domain + j*(d+1);
  // v2: move sp out from the following for loop
  sp = mac3ado_support[i*n + j];
  rs = support[i*n + j];

  // curij: the matrix of relation (i,j)

  // printf ("\nchecking (%d,%d):", i, j );
  // note: curij(x,y) means (x+1, y+1) satisfy constraint (i,j)
  // the first element in domain of i is 1 rather than 0.
  // the content of sp[i,j,x-1] is y(from 1 to d)

  // v2: move curij into for control statement
  for(x = dip[0].next; x != 0; x = dip[x].next){
    viable = false;
    // printf("%d ", x);
    for( y = djp[0].next; y != 0; y = djp[y].next){
	  //cout << "Checking " << x << ',' << y << endl;
      num_cchecks++;
#ifdef EXTENDED_STATISTICS
	  ccheck_levels[curPhase+1]++;
#endif
      if (validtuple(i,j,x,y)) {
	viable = true;
	sp[x-1] = ADOSupport.setSupport(djp,y);
	rs[x-1] = y;
	break;
      }
    }
    if (!viable){
      remove(i,x);
      DELETE = true; // some value in x is removed
    }
  } // all values in i
  return DELETE;
}

bool CSP_Ac3::REVISE3_ADO_propogate(int i, int j)
{
	//cout << "ADO revise propogate: " << i << ',' << j << endl;
  int x, y;
  Domain *dip, *djp;
  SupportNode** sp;
  Support rs;
  int DELETE, viable;

  //extern int curInstance;

  DELETE = false; // no value is removed
  dip = domainOfVar(i); // domain + i*(d+1);
  djp = domainOfVar(j); // domain + j*(d+1);


  for(x = dip[0].next, sp = mac3ado_support[i*n + j],rs = support[i*n+j]; x != 0; x = dip[x].next)
  {
	  num_dchecks++;
#ifdef EXTENDED_STATISTICS
	  dcheck_levels[curPhase+1]++;
#endif
	  if(djp[rs[x-1]].yes)
		  continue;
//      num_cchecks++;
//#ifdef EXTENDED_STATISTICS
//	  ccheck_levels[curPhase+1]++;
//#endif
//	  if(sp[x-1]->value!=0)
//		if(validtuple(i,j,x,sp[x-1]->value))
//			continue;
	  //cout << "Testing ADO support" << endl;
//	  if(sp[x-1]->isValid == true)
//	  {
		  //cout << "ADO support confirmed" << endl;
		  //continue;
//	  }
	  viable=false;
	  //if(sp[x-1]->value==0)
	  //cout << "Ado Residue failed: " << x << endl;
	  //if(sp[x-1]->value!=0)
	  //{
		  for(y= djp[sp[x-1]->value].next; y != 0; y = djp[y].next)
		  {
			  //cout << "Checking " << x << ',' << y << endl;
			num_cchecks++;
#ifdef EXTENDED_STATISTICS
			ccheck_levels[curPhase+1]++;
#endif
			if(validtuple(i,j,x,y))
			{
				//if(sp[x-1]->value==0)
				//	cout << "Successful reintegration." << endl;
				viable=true;
				ADOSupport.removeSupport(djp,sp[x-1]);
				sp[x-1]=ADOSupport.setSupport(djp,y);
				rs[x-1]=y;
				break;
			}
		  }

	  //}
	  if(!viable){
		  remove(i,x);
	  DELETE=true;
	  }
  }
  //cout << "Revise done." << endl;
  return DELETE;
}
#endif

bool CSP_Ac3::mac3_residueD(int var, int value){
  FilterQueue Q(n);
  Domain* dp;
  int dummyValue = headOfDomain();


  dp = domainOfVar(var); 
  for(int curP = dp[0].next; curP != dummyValue;  curP = dp[curP].next){
    if(curP != value) // remove all values except 'value'
      remove(var, curP); 
  }

  Q.enqueue(var); 
  return ac3_residueD_propogate(Q); 
}

bool CSP_Ac3::mac3_residueD(int var){
  FilterQueue Q(n);

  Q.enqueue(var); 
  return ac3_residueD_propogate(Q); 
}

bool CSP_Ac3::mac3_residueD(list<int>& var){
  FilterQueue Q(n);

  for(list<int>::iterator iter=var.begin();iter!=var.end();iter++)
	Q.enqueue(*iter); 
  return ac3_residueD_propogate(Q); 
}

bool CSP_Ac3::ac3_residueD()
{
  //int i, j;
  FilterQueue Q(n); 
  //cout << "Starting AC3 residue" << endl;
  
  if (!ac3_1_residue_init(Q)) return false;
  
  return ac3_residueD_propogate(Q); 
}

bool CSP_Ac3::ac3_residueD_init(FilterQueue& Q) 
{
  int i, j;
  bool acConsistent = true;
  
  //----------------- allocate memory for support ------------
  // decrease the size of support, which improves the efficiency of REVISEnew1
  support = new Support [n*n];
  if (!support){
    printf (" Mem error (support) %d n=%d\n", errno, n);
    exit(-1);
  }
  resD = new Support [n*n];
  if (!resD){
    printf (" Mem error (resD) %d n=%d\n", errno, n);
    exit(-1);
  }
  // allocate memory for support wrt each constraint

  for(i = 0; i < n; i++)
    for(cllp = cross_link_list[i].begin();
	cllp != cross_link_list[i].end(); ++cllp){
      j = *cllp;
      support[i*n + j] = (Support) new int [d];
	  resD[i*n+j] = (Support) new int[d];
      if (!support[i*n+j]){
	printf (" Mem error (support) %d n=%d\n", errno, n);
	exit(-1);
      }   
	  if (!resD[i*n+j]){
	printf (" Mem error (resD) %d n=%d\n", errno, n);
	exit(-1);
      }  
    }
  
  //----------------- populate support[] and check AC of the csp--
  // check all constraints first time
  for(i = 0; i < n; i++)
    for(cllp = cross_link_list[i].begin();
	cllp != cross_link_list[i].end(); ++cllp){
      j = *cllp;
      if (REVISE3_1_residue_init(i,j)){
	if (empty_domain(i)) {
	  acConsistent = false; 
	  goto cleanup;
	}
	Q.enqueue(i); 
      }
    }
 cleanup:
  numOfRemovedValuesB4Propogation = num_removed_values;
  return acConsistent; //so far, the CSP is Arc-consistent
}

bool CSP_Ac3::ac3_residueD_propogate(FilterQueue& Q) {

  if(autofail)
  {
	  autofail=false;
	  return false;
  }
  // variables i and j
  int i, j;

  // std::cout << "removed value is %d \npropagation is on ...", num_removed_values);
  while ( !Q.empty()){
    Q.dequeue(j);

    for(cllp = cross_link_list[j].begin();
	cllp != cross_link_list[j].end(); ++cllp){
      i = *cllp;

      if (isAssigned(i)) continue; // var i being instantiated, ommit it

      if (REVISE3_residueD_propogate(i,j)){
	if (empty_domain(i)) return false;

	//enq_neighbours(i, j);
	Q.enqueue(i);
      } // the domain of i is revised
    } // all neigbouring variables of var j
  } // propogate all the vars in Q

  return true;
}


bool CSP_Ac3::REVISE3_residueD_propogate(int i, int j)
{
  int x, y;
  Domain *dip, *djp;
  Support sp,rs;
  int DELETE, viable;

  DELETE = false; // no value is removed
  dip = domainOfVar(i); // domain + i*(d+1);
  djp = domainOfVar(j); // domain + j*(d+1);

  // curij: the matrix of relation (i,j)
  // std::cout << "i=" << i << " j=" << j << " x=" << x << '\n';
  //  if( (x > 30) || (x <= 0)) 
  //    std::cout << "x=" << x << " is spoiled\n"; 
  //  if ((y == 30) || (y == 0)){
  //    std::cout << "support is spoiled\n"; 
  //    std::cout << "i=" << i << " j=" << j << " x=" << x << " y=" << y << '\n';
  //  }

  // printf ("\nchecking (%d,%d):", i, j );
  for(x = dip[0].next, sp = support[i*n + j],rs = resD[i*n + j]; x != 0; x = dip[x].next){
    
    y = sp[x-1];
	num_dchecks++;
#ifdef EXTENDED_STATISTICS
	dcheck_levels[curPhase+1]++;
#endif
    if (! djp[y].yes){ // is the support of x no longer valid?
		y = rs[x-1];
		num_dchecks++;
#ifdef EXTENDED_STATISTICS
		dcheck_levels[curPhase+1]++;
#endif
		if(!djp[y].yes) {
			viable = false;
			 // we start to search a support from scratch
			 for( y = djp[0].next; y != 0; y = djp[y].next){
				num_cchecks++;
#ifdef EXTENDED_STATISTICS
			   ccheck_levels[curPhase+1]++;
#endif
				if (validtuple(i,j,x,y)) { //if y is valid 
				  viable = true;
				  rs[x-1]=sp[x-1]; //remember primary support in secondary cell
				 sp[x-1] = y; // remember this support
				 break;
				}
			 }
		
	     if (!viable){ // no support
			remove(i,x);
			DELETE = true; // some value in x is removed
		 }
		} //both residue failed
		else		 //primary residue failed, secondary succeeded.
		{
			int temp=sp[x-1];
			sp[x-1]=rs[x-1];
			rs[x-1]=temp;
		}
    } // else x is supported

  } // all values in i
  return DELETE; 
}



bool CSP_Ac3::mac3_1_residue(int var, int value){
  FilterQueue Q(n);
  Domain* dp;
  int dummyValue = headOfDomain();


  dp = domainOfVar(var); 
  for(int curP = dp[0].next; curP != dummyValue;  curP = dp[curP].next){
    if(curP != value) // remove all values except 'value'
      remove(var, curP); 
  }

  Q.enqueue(var); 
  return ac3_1_residue_propogate(Q); 
}

bool CSP_Ac3::mac3_1_residue(int var){
  FilterQueue Q(n);

  Q.enqueue(var); 
  return ac3_1_residue_propogate(Q); 
}

bool CSP_Ac3::mac3_1_residue(list<int>& var){
  FilterQueue Q(n);

  for(list<int>::iterator iter=var.begin();iter!=var.end();iter++)
	Q.enqueue(*iter); 
  return ac3_1_residue_propogate(Q); 
}


bool CSP_Ac3::ac3_1_residue()
{
  //int i, j;
  FilterQueue Q(n); 
  //cout << "Starting AC3 residue" << endl;
  
  if (!ac3_1_residue_init(Q)) return false;
  
  return ac3_1_residue_propogate(Q); 
}

bool CSP_Ac3::ac3_1_residue_init(FilterQueue& Q) 
{
  int i, j;
  bool acConsistent = true;
  
  //----------------- allocate memory for support ------------
  // decrease the size of support, which improves the efficiency of REVISEnew1
  support = new Support [n*n];
  if (!support){
    printf (" Mem error (support) %d n=%d\n", errno, n);
    exit(-1);
  }
  resD = new Support [n*n];
  if (!resD){
    printf (" Mem error (resD) %d n=%d\n", errno, n);
    exit(-1);
  }
  // allocate memory for support wrt each constraint

  for(i = 0; i < n; i++)
    for(cllp = cross_link_list[i].begin();
	cllp != cross_link_list[i].end(); ++cllp){
      j = *cllp;
      support[i*n + j] = (Support) new int [d];
	  resD[i*n+j] = (Support) new int[d];
      if (!support[i*n+j]){
	printf (" Mem error (support) %d n=%d\n", errno, n);
	exit(-1);
      }   
	  if (!resD[i*n+j]){
	printf (" Mem error (resD) %d n=%d\n", errno, n);
	exit(-1);
      }  
    }
  
  //----------------- populate support[] and check AC of the csp--
  // check all constraints first time
  for(i = 0; i < n; i++)
    for(cllp = cross_link_list[i].begin();
	cllp != cross_link_list[i].end(); ++cllp){
      j = *cllp;
      if (REVISE3_1_residue_init(i,j)){
	if (empty_domain(i)) {
	  acConsistent = false; 
	  goto cleanup;
	}
	Q.enqueue(i); 
      }
    }
 cleanup:
  numOfRemovedValuesB4Propogation = num_removed_values;
  return acConsistent; //so far, the CSP is Arc-consistent
}

bool CSP_Ac3::ac3_1_residue_propogate(FilterQueue& Q) {

  if(autofail)
  {
	  autofail=false;
	  return false;
  }
  // variables i and j
  int i, j;

  // std::cout << "removed value is %d \npropagation is on ...", num_removed_values);
  while ( !Q.empty()){
    Q.dequeue(j);

    for(cllp = cross_link_list[j].begin();
	cllp != cross_link_list[j].end(); ++cllp){
      i = *cllp;

      if (isAssigned(i)) continue; // var i being instantiated, ommit it

      if (REVISE3_1_residue_propogate(i,j)){
	if (empty_domain(i)) return false;

	//enq_neighbours(i, j);
	Q.enqueue(i);
      } // the domain of i is revised
    } // all neigbouring variables of var j
  } // propogate all the vars in Q

  return true;
}


bool CSP_Ac3::REVISE3_1_residue_init(int i, int j)
{
  int x, y;
  Domain *dip, *djp;
  Support sp,rs;
  bool DELETE, viable;

  DELETE = false; // no value is removed
  dip = domainOfVar(i); //domain + i*(d+1);
  djp = domainOfVar(j); //domain + j*(d+1);
  // v2: move sp out from the following for loop
  sp = support[i*n + j] ;
  rs = resD[i*n + j];

  // curij: the matrix of relation (i,j)

  // printf ("\nchecking (%d,%d):", i, j );
  // note: curij(x,y) means (x+1, y+1) satisfy constraint (i,j)
  // the first element in domain of i is 1 rather than 0.
  // the content of sp[i,j,x-1] is y(from 1 to d)

  // v2: move curij into for control statement
  for(x = dip[0].next; x != 0; x = dip[x].next){
    viable = false;
    // printf("%d ", x);
    for( y = djp[0].next; y != 0; y = djp[y].next){
      num_cchecks++;
#ifdef EXTENDED_STATISTICS
	  ccheck_levels[curPhase+1]++;
#endif
      if (validtuple(i,j,x,y)) {
	viable = true;
	sp[x-1] = y;
	rs[x-1] = y;
	break;
      }
    }
    if (!viable){
      remove(i,x);
      DELETE = true; // some value in x is removed
    }
  } // all values in i
  return DELETE;
}


bool CSP_Ac3::REVISE3_1_residue_propogate(int i, int j)
{
  int x, y;
  Domain *dip, *djp;
  Support sp,rs;
  BackupedSupport backupedSupport;
  int DELETE, viable;

  //extern int curInstance;

  DELETE = false; // no value is removed
  dip = domainOfVar(i); // domain + i*(d+1);
  djp = domainOfVar(j); // domain + j*(d+1);

  // curij: the matrix of relation (i,j)
  // std::cout << "i=" << i << " j=" << j << " x=" << x << '\n';
  //  if( (x > 30) || (x <= 0)) 
  //    std::cout << "x=" << x << " is spoiled\n"; 
  //  if ((y == 30) || (y == 0)){
  //    std::cout << "support is spoiled\n"; 
  //    std::cout << "i=" << i << " j=" << j << " x=" << x << " y=" << y << '\n';
  //  }

  // printf ("\nchecking (%d,%d):", i, j );
  for(x = dip[0].next, sp = support[i*n + j],rs=resD[i*n+j]; x != 0; x = dip[x].next){
    
    y = rs[x-1];
	  num_dchecks++;
#ifdef EXTENDED_STATISTICS
	  dcheck_levels[curPhase+1]++;
#endif
    if (! djp[y].yes){ // check residue first
		y = sp[x-1];
		num_dchecks++;
	#ifdef EXTENDED_STATISTICS
		dcheck_levels[curPhase+1]++;
	#endif
		if (! djp[y].yes){ // is the support of x no longer valid?
		viable = false;
		for( y = djp[y].next; y != 0; y = djp[y].next){
			num_dchecks++;
	#ifdef EXTENDED_STATISTICS
			dcheck_levels[curPhase+1];
	#endif
			if (djp[y].yes) break;
		}

		for( ; y != 0; y = djp[y].next){
		// if ((djp[y].yes) && (validtuple(i,j,x,y))) { //if y is valid

		num_cchecks++;
	#ifdef EXTENDED_STATISTICS
		ccheck_levels[curPhase+1]++;
	#endif
		if (validtuple(i,j,x,y)) { 
			viable = true;
			//--------------------backup the old support--------------
		    
			backupedSupport.varI = i;
			backupedSupport.varJ = j;
			backupedSupport.value = x;
			backupedSupport.support = sp[x-1]; 
			if( sp[x-1] == 0) 
			cout << "its already spoiled before backup: \n";
			backupedSupport.phase = curPhase; // curPhase defined in class CSP
			previousSupports.push(backupedSupport); 
			//-------------------- end of backup ---------------------
			sp[x-1] = y; // remember this support
			rs[x-1] = y;
			break;
		}

		}
      if (!viable){ // no support
	remove(i,x);
	DELETE = true; // some value in x is removed
      }
		} // supported by record
    } // supported by residue
  } // all values in i
  return DELETE; 
}




bool CSP_Ac3::mac3_RresidueD(int var, int value){
  FilterQueue Q(n);
  Domain* dp;
  int dummyValue = headOfDomain();


  dp = domainOfVar(var); 
  for(int curP = dp[0].next; curP != dummyValue;  curP = dp[curP].next){
    if(curP != value) // remove all values except 'value'
      remove(var, curP); 
  }

  Q.enqueue(var); 
  return ac3_RresidueD_propogate(Q); 
}

bool CSP_Ac3::mac3_RresidueD(int var){
  FilterQueue Q(n);

  Q.enqueue(var); 
  return ac3_RresidueD_propogate(Q); 
}

bool CSP_Ac3::mac3_RresidueD(list<int>& var){
  FilterQueue Q(n);

  for(list<int>::iterator iter=var.begin();iter!=var.end();iter++)
	Q.enqueue(*iter); 
  return ac3_RresidueD_propogate(Q); 
}


bool CSP_Ac3::ac3_RresidueD()
{
  //int i, j;
  FilterQueue Q(n); 
  //cout << "Starting AC3 residue" << endl;
  
  if (!ac3_residueD_init(Q)) return false;
  
  return ac3_RresidueD_propogate(Q); 
}

bool CSP_Ac3::ac3_RresidueD_propogate(FilterQueue& Q) {

  if(autofail)
  {
	  autofail=false;
	  return false;
  }
  // variables i and j
  int i, j;

  // std::cout << "removed value is %d \npropagation is on ...", num_removed_values);
  while ( !Q.empty()){
    Q.dequeue(j);

    for(cllp = cross_link_list[j].begin();
	cllp != cross_link_list[j].end(); ++cllp){
      i = *cllp;

      if (isAssigned(i)) continue; // var i being instantiated, ommit it

      if (REVISE3_RresidueD_propogate(i,j)){
	if (empty_domain(i)) return false;

	//enq_neighbours(i, j);
	Q.enqueue(i);
      } // the domain of i is revised
    } // all neigbouring variables of var j
  } // propogate all the vars in Q

  return true;
}


bool CSP_Ac3::REVISE3_RresidueD_propogate(int i, int j)
{
  int x, y;
  Domain *dip, *djp;
  Support sp,rs;
  int DELETE, viable;

  DELETE = false; // no value is removed
  dip = domainOfVar(i); // domain + i*(d+1);
  djp = domainOfVar(j); // domain + j*(d+1);

  // curij: the matrix of relation (i,j)
  // std::cout << "i=" << i << " j=" << j << " x=" << x << '\n';
  //  if( (x > 30) || (x <= 0)) 
  //    std::cout << "x=" << x << " is spoiled\n"; 
  //  if ((y == 30) || (y == 0)){
  //    std::cout << "support is spoiled\n"; 
  //    std::cout << "i=" << i << " j=" << j << " x=" << x << " y=" << y << '\n';
  //  }

  // printf ("\nchecking (%d,%d):", i, j );
  for(x = dip[0].next, sp = support[i*n + j],rs = resD[i*n + j]; x != 0; x = dip[x].next){
    
    y = sp[x-1];
	num_dchecks++;
#ifdef EXTENDED_STATISTICS
	dcheck_levels[curPhase+1]++;
#endif
    if (! djp[y].yes){ // is the support of x no longer valid?
		y = rs[x-1];
		num_dchecks++;
#ifdef EXTENDED_STATISTICS
		dcheck_levels[curPhase+1]++;
#endif
		if(!djp[y].yes) {
			viable = false;
			 // we start to search a support from scratch
			 for( y = djp[0].next; y != 0; y = djp[y].next){
				num_cchecks++;
#ifdef EXTENDED_STATISTICS
			   ccheck_levels[curPhase+1]++;
#endif
				if (validtuple(i,j,x,y)) { //if y is valid 
				  viable = true;
				  int remove=rand()%2;
				  if(remove)
					rs[x-1]= y; //random setting of y
				  else
					sp[x-1]= y; 
				 break;
				}
			 }
		
	     if (!viable){ // no support
			remove(i,x);
			DELETE = true; // some value in x is removed
		 }
		} //both residue failed
		else		 //primary residue failed, secondary succeeded.
		{
		}
    } // else x is supported

  } // all values in i
  return DELETE; 
}





bool CSP_Ac3::mac3_AresidueD(int var, int value){
  FilterQueue Q(n);
  Domain* dp;
  int dummyValue = headOfDomain();


  dp = domainOfVar(var); 
  for(int curP = dp[0].next; curP != dummyValue;  curP = dp[curP].next){
    if(curP != value) // remove all values except 'value'
      remove(var, curP); 
  }

  Q.enqueue(var); 
  return ac3_AresidueD_propogate(Q); 
}

bool CSP_Ac3::mac3_AresidueD(int var){
  FilterQueue Q(n);

  Q.enqueue(var); 
  return ac3_AresidueD_propogate(Q); 
}

bool CSP_Ac3::mac3_AresidueD(list<int>& var){
  FilterQueue Q(n);

  for(list<int>::iterator iter=var.begin();iter!=var.end();iter++)
	Q.enqueue(*iter); 
  return ac3_AresidueD_propogate(Q); 
}


bool CSP_Ac3::ac3_AresidueD()
{
  //int i, j;
  FilterQueue Q(n); 
  //cout << "Starting AC3 residue" << endl;
  
  if (!ac3_residueD_init(Q)) return false;
  
  return ac3_AresidueD_propogate(Q); 
}

bool CSP_Ac3::ac3_AresidueD_propogate(FilterQueue& Q) {

  if(autofail)
  {
	  autofail=false;
	  return false;
  }
  // variables i and j
  int i, j;

  // std::cout << "removed value is %d \npropagation is on ...", num_removed_values);
  while ( !Q.empty()){
    Q.dequeue(j);

    for(cllp = cross_link_list[j].begin();
	cllp != cross_link_list[j].end(); ++cllp){
      i = *cllp;

      if (isAssigned(i)) continue; // var i being instantiated, ommit it

      if (REVISE3_AresidueD_propogate(i,j)){
	if (empty_domain(i)) return false;

	//enq_neighbours(i, j);
	Q.enqueue(i);
      } // the domain of i is revised
    } // all neigbouring variables of var j
  } // propogate all the vars in Q

  return true;
}


bool CSP_Ac3::REVISE3_AresidueD_propogate(int i, int j)
{
  int x, y;
  Domain *dip, *djp;
  Support sp,rs;
  int DELETE, viable;

  DELETE = false; // no value is removed
  dip = domainOfVar(i); // domain + i*(d+1);
  djp = domainOfVar(j); // domain + j*(d+1);

  // curij: the matrix of relation (i,j)
  // std::cout << "i=" << i << " j=" << j << " x=" << x << '\n';
  //  if( (x > 30) || (x <= 0)) 
  //    std::cout << "x=" << x << " is spoiled\n"; 
  //  if ((y == 30) || (y == 0)){
  //    std::cout << "support is spoiled\n"; 
  //    std::cout << "i=" << i << " j=" << j << " x=" << x << " y=" << y << '\n';
  //  }

  // printf ("\nchecking (%d,%d):", i, j );
  for(x = dip[0].next, sp = support[i*n + j],rs = resD[i*n + j]; x != 0; x = dip[x].next){
    
    y = sp[x-1];
	num_dchecks++;
#ifdef EXTENDED_STATISTICS
	dcheck_levels[curPhase+1]++;
#endif
    if (! djp[y].yes){ // is the support of x no longer valid?
		y = rs[x-1];
		num_dchecks++;
#ifdef EXTENDED_STATISTICS
		dcheck_levels[curPhase+1]++;
#endif
		if(!djp[y].yes) {
			viable = false;
			 // we start to search a support from scratch
			 for( y = djp[0].next; y != 0; y = djp[y].next){
				num_cchecks++;
#ifdef EXTENDED_STATISTICS
			   ccheck_levels[curPhase+1]++;
#endif
				if (validtuple(i,j,x,y)) { //if y is valid 
				  viable = true;
				  rs[x-1]= y; //remember new support in newest (ANTI)
				  break;
				}
			 }
		
	     if (!viable){ // no support
			remove(i,x);
			DELETE = true; // some value in x is removed
		 }
		} //both residue failed
		else		 //primary residue failed, secondary succeeded.
		{
		}
    } // else x is supported
	else  //keep most recently used at back
	{
		int temp=sp[x-1];
		sp[x-1]=rs[x-1];
		rs[x-1]=temp;
	}
  } // all values in i
  return DELETE; 
}





bool CSP_Ac3::mac3_AFresidueD(int var, int value){
  FilterQueue Q(n);
  Domain* dp;
  int dummyValue = headOfDomain();


  dp = domainOfVar(var); 
  for(int curP = dp[0].next; curP != dummyValue;  curP = dp[curP].next){
    if(curP != value) // remove all values except 'value'
      remove(var, curP); 
  }

  Q.enqueue(var); 
  return ac3_AFresidueD_propogate(Q); 
}

bool CSP_Ac3::mac3_AFresidueD(int var){
  FilterQueue Q(n);

  Q.enqueue(var); 
  return ac3_AFresidueD_propogate(Q); 
}

bool CSP_Ac3::mac3_AFresidueD(list<int>& var){
  FilterQueue Q(n);

  for(list<int>::iterator iter=var.begin();iter!=var.end();iter++)
	Q.enqueue(*iter); 
  return ac3_AFresidueD_propogate(Q); 
}


bool CSP_Ac3::ac3_AFresidueD()
{
  //int i, j;
  FilterQueue Q(n); 
  //cout << "Starting AC3 residue" << endl;
  
  if (!ac3_FresidueD_init(Q)) return false;
  
  return ac3_AFresidueD_propogate(Q); 
}

bool CSP_Ac3::ac3_AFresidueD_propogate(FilterQueue& Q) {

  if(autofail)
  {
	  autofail=false;
	  return false;
  }
  // variables i and j
  int i, j;

  // std::cout << "removed value is %d \npropagation is on ...", num_removed_values);
  while ( !Q.empty()){
    Q.dequeue(j);

    for(cllp = cross_link_list[j].begin();
	cllp != cross_link_list[j].end(); ++cllp){
      i = *cllp;

      if (isAssigned(i)) continue; // var i being instantiated, ommit it

      if (REVISE3_AFresidueD_propogate(i,j)){
	if (empty_domain(i)) return false;

	//enq_neighbours(i, j);
	Q.enqueue(i);
      } // the domain of i is revised
    } // all neigbouring variables of var j
  } // propogate all the vars in Q

  return true;
}


bool CSP_Ac3::REVISE3_AFresidueD_propogate(int i, int j)
{
  int x, y;
  Domain *dip, *djp;
  Support sp,rs,f1,f2;
  int DELETE, viable;

  DELETE = false; // no value is removed
  dip = domainOfVar(i); // domain + i*(d+1);
  djp = domainOfVar(j); // domain + j*(d+1);

  // curij: the matrix of relation (i,j)
  // std::cout << "i=" << i << " j=" << j << " x=" << x << '\n';
  //  if( (x > 30) || (x <= 0)) 
  //    std::cout << "x=" << x << " is spoiled\n"; 
  //  if ((y == 30) || (y == 0)){
  //    std::cout << "support is spoiled\n"; 
  //    std::cout << "i=" << i << " j=" << j << " x=" << x << " y=" << y << '\n';
  //  }

  // printf ("\nchecking (%d,%d):", i, j );
  for(x = dip[0].next, sp = support[i*n + j],rs = resD[i*n + j],f1 = fit1[i*n + j],f2 = fit1[i*n + j]; x != 0; x = dip[x].next){
    
    y = sp[x-1];
	num_dchecks++;
#ifdef EXTENDED_STATISTICS
	dcheck_levels[curPhase+1]++;
#endif
    if (! djp[y].yes){ // is the primary support of x no longer valid?
		f1[x-1]--;
		y = rs[x-1];
		num_dchecks++;
#ifdef EXTENDED_STATISTICS
		dcheck_levels[curPhase+1]++;
#endif
		if(!djp[y].yes) { //is the secondary support of x no longer valid?
			f2[x-1]--;
			viable = false;
			 // we start to search a support from scratch
			 for( y = djp[0].next; y != 0; y = djp[y].next){
				num_cchecks++;
#ifdef EXTENDED_STATISTICS
			   ccheck_levels[curPhase+1]++;
#endif
				if (validtuple(i,j,x,y)) { //if y is valid 
				  viable = true;
				  if(f1[x-1]>1)
				  {
					rs[x-1]=sp[x-1]; //remember primary support in secondary cell
					sp[x-1] = y; // remember this support
					f2[x-1]=f1[x-1];
					f1[x-1]=1;
				  }
				  else
				  {
					rs[x-1]=y;
				    f2[x-1]=1;
				  }				    
				  break;
				}
			 }
		
	     if (!viable){ // no support
			remove(i,x);
			DELETE = true; // some value in x is removed
		 }
		} //both residue failed
		else		 //primary residue failed, secondary succeeded.
		{
			f2[x-1]++;
		}
    } // else x is supported
	else
	{
		f1[x-1]++;
		if(f1[x-1]>f2[x-1])
			{
				int temp=sp[x-1];
				sp[x-1]=rs[x-1];
				rs[x-1]=temp;

				temp=f1[x-1];
				f1[x-1]=f2[x-1];
				f2[x-1]=temp;
			}
	}

  } // all values in i
  return DELETE; 
}








bool CSP_Ac3::mac3_SFresidueD(int var, int value){
  FilterQueue Q(n);
  Domain* dp;
  int dummyValue = headOfDomain();


  dp = domainOfVar(var); 
  for(int curP = dp[0].next; curP != dummyValue;  curP = dp[curP].next){
    if(curP != value) // remove all values except 'value'
      remove(var, curP); 
  }

  Q.enqueue(var); 
  return ac3_SFresidueD_propogate(Q); 
}

bool CSP_Ac3::mac3_SFresidueD(int var){
  FilterQueue Q(n);

  Q.enqueue(var); 
  return ac3_SFresidueD_propogate(Q); 
}

bool CSP_Ac3::mac3_SFresidueD(list<int>& var){
  FilterQueue Q(n);

  for(list<int>::iterator iter=var.begin();iter!=var.end();iter++)
	Q.enqueue(*iter); 
  return ac3_SFresidueD_propogate(Q); 
}


bool CSP_Ac3::ac3_SFresidueD()
{
  //int i, j;
  FilterQueue Q(n); 
  //cout << "Starting AC3 residue" << endl;
  
  if (!ac3_DFresidueD_init(Q)) return false;
  
  return ac3_SFresidueD_propogate(Q); 
}

bool CSP_Ac3::ac3_SFresidueD_propogate(FilterQueue& Q) {

  if(autofail)
  {
	  autofail=false;
	  return false;
  }
  // variables i and j
  int i, j;

  // std::cout << "removed value is %d \npropagation is on ...", num_removed_values);
  while ( !Q.empty()){
    Q.dequeue(j);

    for(cllp = cross_link_list[j].begin();
	cllp != cross_link_list[j].end(); ++cllp){
      i = *cllp;

      if (isAssigned(i)) continue; // var i being instantiated, ommit it

      if (REVISE3_SFresidueD_propogate(i,j)){
	if (empty_domain(i)) return false;

	//enq_neighbours(i, j);
	Q.enqueue(i);
      } // the domain of i is revised
    } // all neigbouring variables of var j
  } // propogate all the vars in Q

  return true;
}


bool CSP_Ac3::REVISE3_SFresidueD_propogate(int i, int j)
{
  int x, y;
  Domain *dip, *djp;
  Support sp,rs,f1,f2;
  int DELETE, viable;

  DELETE = false; // no value is removed
  dip = domainOfVar(i); // domain + i*(d+1);
  djp = domainOfVar(j); // domain + j*(d+1);

  // curij: the matrix of relation (i,j)
  // std::cout << "i=" << i << " j=" << j << " x=" << x << '\n';
  //  if( (x > 30) || (x <= 0)) 
  //    std::cout << "x=" << x << " is spoiled\n"; 
  //  if ((y == 30) || (y == 0)){
  //    std::cout << "support is spoiled\n"; 
  //    std::cout << "i=" << i << " j=" << j << " x=" << x << " y=" << y << '\n';
  //  }

  // printf ("\nchecking (%d,%d):", i, j );
  for(x = dip[0].next, sp = support[i*n + j],rs = resD[i*n + j],f1 = fit1[i*n + j],f2 = fit1[i*n + j]; x != 0; x = dip[x].next){
    
    y = sp[x-1];
	num_dchecks++;
#ifdef EXTENDED_STATISTICS
	dcheck_levels[curPhase+1]++;
#endif
    if (! djp[y].yes){ // is the primary support of x no longer valid?
		y = rs[x-1];
		num_dchecks++;
#ifdef EXTENDED_STATISTICS
		dcheck_levels[curPhase+1]++;
#endif
		if(!djp[y].yes) { //is the secondary support of x no longer valid?
			viable = false;
			 // we start to search a support from scratch
			 for( y = djp[0].next; y != 0; y = djp[y].next){
				num_cchecks++;
#ifdef EXTENDED_STATISTICS
			   ccheck_levels[curPhase+1]++;
#endif
				if (validtuple(i,j,x,y)) { //if y is valid 
				  viable = true;
				
				rs[x-1]= y; // remember this support
				f1[x-1]=curPhase;				    
				  break;
				}
			 }
		
	     if (!viable){ // no support
			remove(i,x);
			DELETE = true; // some value in x is removed
		 }
		} //both residue failed
    } // else x is supported

  } // all values in i
  return DELETE; 
}





bool CSP_Ac3::mac3_FresidueD(int var, int value){
  FilterQueue Q(n);
  Domain* dp;
  int dummyValue = headOfDomain();


  dp = domainOfVar(var); 
  for(int curP = dp[0].next; curP != dummyValue;  curP = dp[curP].next){
    if(curP != value) // remove all values except 'value'
      remove(var, curP); 
  }

  Q.enqueue(var); 
  return ac3_FresidueD_propogate(Q); 
}

bool CSP_Ac3::mac3_FresidueD(int var){
  FilterQueue Q(n);

  Q.enqueue(var); 
  return ac3_FresidueD_propogate(Q); 
}

bool CSP_Ac3::mac3_FresidueD(list<int>& var){
  FilterQueue Q(n);

  for(list<int>::iterator iter=var.begin();iter!=var.end();iter++)
	Q.enqueue(*iter); 
  return ac3_FresidueD_propogate(Q); 
}


bool CSP_Ac3::ac3_FresidueD()
{
  //int i, j;
  FilterQueue Q(n); 
  //cout << "Starting AC3 residue" << endl;
  
  if (!ac3_FresidueD_init(Q)) return false;
  
  return ac3_FresidueD_propogate(Q); 
}


bool CSP_Ac3::ac3_FresidueD_init(FilterQueue& Q) 
{
  int i, j;
  bool acConsistent = true;
  
  //----------------- allocate memory for support ------------
  // decrease the size of support, which improves the efficiency of REVISEnew1
  support = new Support [n*n];
  if (!support){
    printf (" Mem error (support) %d n=%d\n", errno, n);
    exit(-1);
  }
  resD = new Support [n*n];
  if (!resD){
    printf (" Mem error (resD) %d n=%d\n", errno, n);
    exit(-1);
  }
  fit1 = new Support [n*n];
  if (!fit1){
    printf (" Mem error (fit1) %d n=%d\n", errno, n);
    exit(-1);
  }
  fit2 = new Support [n*n];
  if (!fit2){
    printf (" Mem error (fit2) %d n=%d\n", errno, n);
    exit(-1);
  }
  // allocate memory for support wrt each constraint

  for(i = 0; i < n; i++)
    for(cllp = cross_link_list[i].begin();
	cllp != cross_link_list[i].end(); ++cllp){
      j = *cllp;
      support[i*n + j] = (Support) new int [d];
	  resD[i*n+j] = (Support) new int[d];
	  fit1[i*n + j] = (Support) new int [d];
	  fit2[i*n+j] = (Support) new int[d];
      if (!support[i*n+j]){
	printf (" Mem error (support) %d n=%d\n", errno, n);
	exit(-1);
      }   
	  if (!resD[i*n+j]){
	printf (" Mem error (resD) %d n=%d\n", errno, n);
	exit(-1);
      }  
	  if (!fit1[i*n+j]){
		printf (" Mem error (fit1) %d n=%d\n", errno, n);
		exit(-1);
      }   
	  if (!fit2[i*n+j]){
		printf (" Mem error (fit2) %d n=%d\n", errno, n);
		exit(-1);
	  }
    }
  
  //----------------- populate support[] and check AC of the csp--
  // check all constraints first time
  for(i = 0; i < n; i++)
    for(cllp = cross_link_list[i].begin();
	cllp != cross_link_list[i].end(); ++cllp){
      j = *cllp;
      if (REVISE3_FresidueD_init(i,j)){
	if (empty_domain(i)) {
	  acConsistent = false; 
	  goto cleanup;
	}
	Q.enqueue(i); 
      }
    }
 cleanup:
  numOfRemovedValuesB4Propogation = num_removed_values;
  return acConsistent; //so far, the CSP is Arc-consistent
}

bool CSP_Ac3::ac3_FresidueD_propogate(FilterQueue& Q) {

  if(autofail)
  {
	  autofail=false;
	  return false;
  }
  // variables i and j
  int i, j;

  // std::cout << "removed value is %d \npropagation is on ...", num_removed_values);
  while ( !Q.empty()){
    Q.dequeue(j);

    for(cllp = cross_link_list[j].begin();
	cllp != cross_link_list[j].end(); ++cllp){
      i = *cllp;

      if (isAssigned(i)) continue; // var i being instantiated, ommit it

      if (REVISE3_FresidueD_propogate(i,j)){
	if (empty_domain(i)) return false;

	//enq_neighbours(i, j);
	Q.enqueue(i);
      } // the domain of i is revised
    } // all neigbouring variables of var j
  } // propogate all the vars in Q

  return true;
}



bool CSP_Ac3::REVISE3_FresidueD_init(int i, int j)
{
  int x, y;
  Domain *dip, *djp;
  Support sp,rs,f1,f2;
  bool DELETE, viable;

  DELETE = false; // no value is removed
  dip = domainOfVar(i); //domain + i*(d+1);
  djp = domainOfVar(j); //domain + j*(d+1);
  // v2: move sp out from the following for loop
  sp = support[i*n + j] ;
  rs = resD[i*n + j];
  f1 = fit1[i*n + j];
  f2 = fit2[i*n + j];

  // curij: the matrix of relation (i,j)

  // printf ("\nchecking (%d,%d):", i, j );
  // note: curij(x,y) means (x+1, y+1) satisfy constraint (i,j)
  // the first element in domain of i is 1 rather than 0.
  // the content of sp[i,j,x-1] is y(from 1 to d)

  // v2: move curij into for control statement
  for(x = dip[0].next; x != 0; x = dip[x].next){
    viable = false;
    // printf("%d ", x);
    for( y = djp[0].next; y != 0; y = djp[y].next){
      num_cchecks++;
#ifdef EXTENDED_STATISTICS
	  ccheck_levels[curPhase+1]++;
#endif
      if (validtuple(i,j,x,y)) {
	viable = true;
	sp[x-1] = y;
	rs[x-1] = y;
	f1[x-1] = 1;
	f2[x-1] = 1;
	break;
      }
    }
    if (!viable){
      remove(i,x);
      DELETE = true; // some value in x is removed
    }
  } // all values in i
  return DELETE;
}


bool CSP_Ac3::REVISE3_FresidueD_propogate(int i, int j)
{
  int x, y;
  Domain *dip, *djp;
  Support sp,rs,f1,f2;
  int DELETE, viable;

  DELETE = false; // no value is removed
  dip = domainOfVar(i); // domain + i*(d+1);
  djp = domainOfVar(j); // domain + j*(d+1);

  // curij: the matrix of relation (i,j)
  // std::cout << "i=" << i << " j=" << j << " x=" << x << '\n';
  //  if( (x > 30) || (x <= 0)) 
  //    std::cout << "x=" << x << " is spoiled\n"; 
  //  if ((y == 30) || (y == 0)){
  //    std::cout << "support is spoiled\n"; 
  //    std::cout << "i=" << i << " j=" << j << " x=" << x << " y=" << y << '\n';
  //  }

  // printf ("\nchecking (%d,%d):", i, j );
  for(x = dip[0].next, sp = support[i*n + j],rs = resD[i*n + j],f1 = fit1[i*n + j],f2 = fit1[i*n + j]; x != 0; x = dip[x].next){
    
    y = sp[x-1];
	num_dchecks++;
#ifdef EXTENDED_STATISTICS
	dcheck_levels[curPhase+1]++;
#endif
    if (! djp[y].yes){ // is the primary support of x no longer valid?
		f1[x-1]--;
		y = rs[x-1];
		num_dchecks++;
#ifdef EXTENDED_STATISTICS
		dcheck_levels[curPhase+1]++;
#endif
		if(!djp[y].yes) { //is the secondary support of x no longer valid?
			f2[x-1]--;
			viable = false;
			 // we start to search a support from scratch
			 for( y = djp[0].next; y != 0; y = djp[y].next){
				num_cchecks++;
#ifdef EXTENDED_STATISTICS
			   ccheck_levels[curPhase+1]++;
#endif
				if (validtuple(i,j,x,y)) { //if y is valid 
				  viable = true;
				  if(f1[x-1]<1)
				  {
					rs[x-1]=sp[x-1]; //remember primary support in secondary cell
					sp[x-1] = y; // remember this support
					f2[x-1]=f1[x-1];
					f1[x-1]=1;
				  }
				  else
				  {
					rs[x-1]=y;
				    f2[x-1]=1;
				  }				    
				  break;
				}
			 }
		
	     if (!viable){ // no support
			remove(i,x);
			DELETE = true; // some value in x is removed
		 }
		} //both residue failed
		else		 //primary residue failed, secondary succeeded.
		{
			f2[x-1]++;
			if(f2[x-1]>f1[x-1])
			{
				int temp=sp[x-1];
				sp[x-1]=rs[x-1];
				rs[x-1]=temp;

				temp=f1[x-1];
				f1[x-1]=f2[x-1];
				f2[x-1]=temp;
			}
		}
    } // else x is supported
	else
	{
		f1[x-1]++;
	}

  } // all values in i
  return DELETE; 
}









bool CSP_Ac3::mac3_DFresidueD(int var, int value){
  FilterQueue Q(n);
  Domain* dp;
  int dummyValue = headOfDomain();


  dp = domainOfVar(var); 
  for(int curP = dp[0].next; curP != dummyValue;  curP = dp[curP].next){
    if(curP != value) // remove all values except 'value'
      remove(var, curP); 
  }

  Q.enqueue(var); 
  return ac3_DFresidueD_propogate(Q); 
}

bool CSP_Ac3::mac3_DFresidueD(int var){
  FilterQueue Q(n);

  Q.enqueue(var); 
  return ac3_DFresidueD_propogate(Q); 
}

bool CSP_Ac3::mac3_DFresidueD(list<int>& var){
  FilterQueue Q(n);

  for(list<int>::iterator iter=var.begin();iter!=var.end();iter++)
	Q.enqueue(*iter); 
  return ac3_DFresidueD_propogate(Q); 
}


bool CSP_Ac3::ac3_DFresidueD()
{
  //int i, j;
  FilterQueue Q(n); 
  //cout << "Starting AC3 residue" << endl;
  
  if (!ac3_DFresidueD_init(Q)) return false;
  
  return ac3_DFresidueD_propogate(Q); 
}

bool CSP_Ac3::ac3_DFresidueD_init(FilterQueue& Q) 
{
  int i, j;
  bool acConsistent = true;
  
  //----------------- allocate memory for support ------------
  // decrease the size of support, which improves the efficiency of REVISEnew1
  support = new Support [n*n];
  if (!support){
    printf (" Mem error (support) %d n=%d\n", errno, n);
    exit(-1);
  }
  resD = new Support [n*n];
  if (!resD){
    printf (" Mem error (resD) %d n=%d\n", errno, n);
    exit(-1);
  }
  fit1 = new Support [n*n];
  if (!fit1){
    printf (" Mem error (fit1) %d n=%d\n", errno, n);
    exit(-1);
  }
  fit2 = new Support [n*n];
  if (!fit2){
    printf (" Mem error (fit2) %d n=%d\n", errno, n);
    exit(-1);
  }
  // allocate memory for support wrt each constraint

  for(i = 0; i < n; i++)
    for(cllp = cross_link_list[i].begin();
	cllp != cross_link_list[i].end(); ++cllp){
      j = *cllp;
      support[i*n + j] = (Support) new int [d];
	  resD[i*n+j] = (Support) new int[d];
	  fit1[i*n + j] = (Support) new int [d];
	  fit2[i*n+j] = (Support) new int[d];
      if (!support[i*n+j]){
	printf (" Mem error (support) %d n=%d\n", errno, n);
	exit(-1);
      }   
	  if (!resD[i*n+j]){
	printf (" Mem error (resD) %d n=%d\n", errno, n);
	exit(-1);
      }  
	  if (!fit1[i*n+j]){
		printf (" Mem error (fit1) %d n=%d\n", errno, n);
		exit(-1);
      }   
	  if (!fit2[i*n+j]){
		printf (" Mem error (fit2) %d n=%d\n", errno, n);
		exit(-1);
	  }
    }
  
  //----------------- populate support[] and check AC of the csp--
  // check all constraints first time
  for(i = 0; i < n; i++)
    for(cllp = cross_link_list[i].begin();
	cllp != cross_link_list[i].end(); ++cllp){
      j = *cllp;
      if (REVISE3_DFresidueD_init(i,j)){
	if (empty_domain(i)) {
	  acConsistent = false; 
	  goto cleanup;
	}
	Q.enqueue(i); 
      }
    }
 cleanup:
  numOfRemovedValuesB4Propogation = num_removed_values;
  return acConsistent; //so far, the CSP is Arc-consistent
}

bool CSP_Ac3::ac3_DFresidueD_propogate(FilterQueue& Q) {

  if(autofail)
  {
	  autofail=false;
	  return false;
  }
  // variables i and j
  int i, j;

  // std::cout << "removed value is %d \npropagation is on ...", num_removed_values);
  while ( !Q.empty()){
    Q.dequeue(j);

    for(cllp = cross_link_list[j].begin();
	cllp != cross_link_list[j].end(); ++cllp){
      i = *cllp;

      if (isAssigned(i)) continue; // var i being instantiated, ommit it

      if (REVISE3_DFresidueD_propogate(i,j)){
	if (empty_domain(i)) return false;

	//enq_neighbours(i, j);
	Q.enqueue(i);
      } // the domain of i is revised
    } // all neigbouring variables of var j
  } // propogate all the vars in Q

  return true;
}

bool CSP_Ac3::REVISE3_DFresidueD_init(int i, int j)
{
  int x, y;
  Domain *dip, *djp;
  Support sp,rs,f1,f2;
  bool DELETE, viable;

  DELETE = false; // no value is removed
  dip = domainOfVar(i); //domain + i*(d+1);
  djp = domainOfVar(j); //domain + j*(d+1);
  // v2: move sp out from the following for loop
  sp = support[i*n + j] ;
  rs = resD[i*n + j];
  f1 = fit1[i*n + j];
  f2 = fit2[i*n + j];

  // curij: the matrix of relation (i,j)

  // printf ("\nchecking (%d,%d):", i, j );
  // note: curij(x,y) means (x+1, y+1) satisfy constraint (i,j)
  // the first element in domain of i is 1 rather than 0.
  // the content of sp[i,j,x-1] is y(from 1 to d)

  // v2: move curij into for control statement
  for(x = dip[0].next; x != 0; x = dip[x].next){
    viable = false;
    // printf("%d ", x);
    for( y = djp[0].next; y != 0; y = djp[y].next){
      num_cchecks++;
#ifdef EXTENDED_STATISTICS
	  ccheck_levels[curPhase+1]++;
#endif
      if (validtuple(i,j,x,y)) {
	viable = true;
	sp[x-1] = y;
	rs[x-1] = y;
	f1[x-1]=-1;
	f2[x-1]=-1;
	break;
      }
    }
    if (!viable){
      remove(i,x);
      DELETE = true; // some value in x is removed
    }
  } // all values in i
  return DELETE;
}



bool CSP_Ac3::REVISE3_DFresidueD_propogate(int i, int j)
{
  int x, y;
  Domain *dip, *djp;
  Support sp,rs,f1,f2;
  int DELETE, viable;

  DELETE = false; // no value is removed
  dip = domainOfVar(i); // domain + i*(d+1);
  djp = domainOfVar(j); // domain + j*(d+1);

  // curij: the matrix of relation (i,j)
  // std::cout << "i=" << i << " j=" << j << " x=" << x << '\n';
  //  if( (x > 30) || (x <= 0)) 
  //    std::cout << "x=" << x << " is spoiled\n"; 
  //  if ((y == 30) || (y == 0)){
  //    std::cout << "support is spoiled\n"; 
  //    std::cout << "i=" << i << " j=" << j << " x=" << x << " y=" << y << '\n';
  //  }

  // printf ("\nchecking (%d,%d):", i, j );
  for(x = dip[0].next, sp = support[i*n + j],rs = resD[i*n + j],f1 = fit1[i*n + j],f2 = fit1[i*n + j]; x != 0; x = dip[x].next){
    
    y = sp[x-1];
	num_dchecks++;
#ifdef EXTENDED_STATISTICS
	dcheck_levels[curPhase+1]++;
#endif
    if (! djp[y].yes){ // is the primary support of x no longer valid?
		y = rs[x-1];
		num_dchecks++;
#ifdef EXTENDED_STATISTICS
		dcheck_levels[curPhase+1]++;
#endif
		if(!djp[y].yes) { //is the secondary support of x no longer valid?
			viable = false;
			 // we start to search a support from scratch
			 for( y = djp[0].next; y != 0; y = djp[y].next){
				num_cchecks++;
#ifdef EXTENDED_STATISTICS
			   ccheck_levels[curPhase+1]++;
#endif
				if (validtuple(i,j,x,y)) { //if y is valid 
				  viable = true;
					if(f1[x-1]<curPhase)
					{
						rs[x-1]= sp[x-1]; // remember this support
						sp[x-1]= y;
						f2[x-1]=f1[x-1];
						f1[x-1]=curPhase;
					}
					else
					{
						rs[x-1]=y;
						f2[x-1]=curPhase;
					}	
					break;	
				}
			 }
		
	     if (!viable){ // no support
			remove(i,x);
			DELETE = true; // some value in x is removed
		 }
		} //both residue failed
    } // else x is supported

  } // all values in i
  return DELETE; 
}

